Submission #3370313
Source Code Expand
#include <bits/stdc++.h> #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto& (a): (b)) #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<<endl #define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl #define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl #define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl #define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl #define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl #define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl using namespace std; typedef pair<int,int> P; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<double> vd; typedef vector<P> vp; typedef vector<string> vs; const int MAX_N = 500; int n,m; class mat { public: bitset<MAX_N>* a; mat(){ a = new bitset<MAX_N>[MAX_N]; } mat operator*(const mat& m) const { mat ans; for(int i = 0; i < MAX_N; i++){ for(int j = 0; j < MAX_N; j++){ if(this->a[i][j] == 0) continue; ans.a[i] |= m.a[j]; } } return ans; } }; bool possible(mat m, ll cnt) { mat res; rep(i,n){ res.a[i].set(i); } while(cnt){ if(cnt & 1){ res = res*m; } cnt >>= 1; m = m*m; } return ((int)res.a[0].count() == n); } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n >> m; mat A; rep(i,m){ int x,y; cin >> x >> y; A.a[x-1].set(y-1); } ll l = 0, r = 50000000000LL; if(!possible(A,r)){ cout << "-1\n"; return 0; } while(r-l>1){ ll mid = (l+r)/2; if(possible(A,mid)){ r = mid; }else{ l = mid; } } cout << r%MOD << "\n"; return 0; }
Submission Info
Submission Time | |
---|---|
Task | I - Revenge of the Endless BFS |
User | kopricky |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 2515 Byte |
Status | AC |
Exec Time | 1890 ms |
Memory | 42112 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_sample_00, 00_sample_01, 00_sample_02, 10_small_0, 10_small_1, 10_small_2, 10_small_3, 10_small_4, 20_random_0, 20_random_1, 20_random_2, 20_random_3, 20_random_4, 20_random_5, 20_random_6, 20_random_7, 20_random_8, 20_random_9, 90_cycle_like_0, 90_cycle_like_1, 90_cycle_like_2, 90_cycle_like_3, 90_cycle_like_4, 91_cycle_like_dense_0, 91_cycle_like_dense_1, 91_cycle_like_dense_2, 91_cycle_like_dense_3, 91_cycle_like_dense_4, 91_cycle_like_dense_5, 91_cycle_like_dense_6, 91_cycle_like_dense_7, 91_cycle_like_dense_8, 91_cycle_like_dense_9, 99_ng_max_dense_0, 99_ng_max_odd_prime_0, 99_ng_max_odd_prime_dense_0, 99_ng_max_odd_prime_dense_1, 99_ng_max_odd_prime_dense_2, 99_ng_max_odd_prime_dense_3, 99_ng_max_odd_prime_dense_4, 99_ng_max_prime_0, 99_ok_max_0 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_00 | AC | 15 ms | 1920 KB |
00_sample_01 | AC | 273 ms | 33280 KB |
00_sample_02 | AC | 272 ms | 33024 KB |
10_small_0 | AC | 15 ms | 1920 KB |
10_small_1 | AC | 270 ms | 33024 KB |
10_small_2 | AC | 271 ms | 33024 KB |
10_small_3 | AC | 270 ms | 33024 KB |
10_small_4 | AC | 15 ms | 1920 KB |
20_random_0 | AC | 285 ms | 33024 KB |
20_random_1 | AC | 527 ms | 33024 KB |
20_random_2 | AC | 1162 ms | 33024 KB |
20_random_3 | AC | 328 ms | 33024 KB |
20_random_4 | AC | 529 ms | 33024 KB |
20_random_5 | AC | 1340 ms | 33180 KB |
20_random_6 | AC | 1718 ms | 33024 KB |
20_random_7 | AC | 715 ms | 33024 KB |
20_random_8 | AC | 1431 ms | 33024 KB |
20_random_9 | AC | 295 ms | 33024 KB |
90_cycle_like_0 | AC | 962 ms | 41600 KB |
90_cycle_like_1 | AC | 950 ms | 41344 KB |
90_cycle_like_2 | AC | 932 ms | 40480 KB |
90_cycle_like_3 | AC | 957 ms | 42112 KB |
90_cycle_like_4 | AC | 956 ms | 41856 KB |
91_cycle_like_dense_0 | AC | 1890 ms | 36480 KB |
91_cycle_like_dense_1 | AC | 1056 ms | 40960 KB |
91_cycle_like_dense_2 | AC | 985 ms | 40960 KB |
91_cycle_like_dense_3 | AC | 978 ms | 40832 KB |
91_cycle_like_dense_4 | AC | 1774 ms | 37504 KB |
91_cycle_like_dense_5 | AC | 1247 ms | 39808 KB |
91_cycle_like_dense_6 | AC | 1791 ms | 38656 KB |
91_cycle_like_dense_7 | AC | 1248 ms | 39040 KB |
91_cycle_like_dense_8 | AC | 1347 ms | 39552 KB |
91_cycle_like_dense_9 | AC | 1460 ms | 38912 KB |
99_ng_max_dense_0 | AC | 120 ms | 1920 KB |
99_ng_max_odd_prime_0 | AC | 15 ms | 1920 KB |
99_ng_max_odd_prime_dense_0 | AC | 87 ms | 1920 KB |
99_ng_max_odd_prime_dense_1 | AC | 67 ms | 1920 KB |
99_ng_max_odd_prime_dense_2 | AC | 109 ms | 1920 KB |
99_ng_max_odd_prime_dense_3 | AC | 96 ms | 1920 KB |
99_ng_max_odd_prime_dense_4 | AC | 57 ms | 1920 KB |
99_ng_max_prime_0 | AC | 15 ms | 1920 KB |
99_ok_max_0 | AC | 845 ms | 41472 KB |