Submission #3768126
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; template <int COL_SIZE> class mat { private: // (or, and) の意味での積(正方かつ対称行列に限る(重みなし無向グラフの隣接行列とか)) mat operator*(const mat& m) const { mat ans; for(int i = 0; i < COL_SIZE; i++){ for(int j = 0; j < COL_SIZE; j++){ if(this->a[i][j] == 0) continue; ans.a[i] |= m.a[j]; } } return ans; } public: bitset<COL_SIZE>* a; int r; // 正方行列の場合 mat(){ a = new bitset<COL_SIZE>[COL_SIZE]; } // 一般の行列の場合 mat(int row_size) : r(row_size){ a = new bitset<COL_SIZE>[r]; } int rank() const { int res = 0; mat<COL_SIZE> b(r); for(int i = 0; i < r; i++) b[i] = a[i]; for(int i = 0; i < COL_SIZE; i++){ if(res == r) return res; int pivot = res; if(!b[pivot][i]){ for(int j = res + 1; j < r; j++){ if(b[j][i]){ pivot = j; break; } } if(!b[pivot][i]) continue; swap(b[pivot], b[res]); } for(int j = res + 1; j < r; j++){ if(b[j][i]) b[j] ^= b[res]; } res++; } return res; } inline const bitset<COL_SIZE>& operator[](size_t index) const { return a[index]; } inline bitset<COL_SIZE>& operator[](size_t index){ return a[index]; } friend mat pow(mat m, long long cnt){ mat res; for(int i = 0; i < COL_SIZE; i++) res[i][i] = 1; while(cnt){ if(cnt & 1){ res = res * m; } m = m * m; cnt >>= 1; } return res; } }; int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n >> m; mat<MAX_N> A; rep(i,m){ int x,y; cin >> x >> y; A[x-1][y-1] = 1; } ll l = 0, r = 50000000000LL; if((int)pow(A,r)[0].count() != n){ cout << "-1\n"; return 0; } while(r-l>1){ ll mid = (l+r)/2; if((int)pow(A,mid)[0].count() == n){ 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 | 3828 Byte |
Status | AC |
Exec Time | 1687 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 | 278 ms | 33280 KB |
00_sample_02 | AC | 275 ms | 33024 KB |
10_small_0 | AC | 15 ms | 1920 KB |
10_small_1 | AC | 275 ms | 33024 KB |
10_small_2 | AC | 277 ms | 33024 KB |
10_small_3 | AC | 277 ms | 33024 KB |
10_small_4 | AC | 15 ms | 1920 KB |
20_random_0 | AC | 288 ms | 33024 KB |
20_random_1 | AC | 491 ms | 33024 KB |
20_random_2 | AC | 1022 ms | 33024 KB |
20_random_3 | AC | 323 ms | 33024 KB |
20_random_4 | AC | 492 ms | 33024 KB |
20_random_5 | AC | 1170 ms | 33024 KB |
20_random_6 | AC | 1485 ms | 33024 KB |
20_random_7 | AC | 648 ms | 33024 KB |
20_random_8 | AC | 1243 ms | 33024 KB |
20_random_9 | AC | 296 ms | 33024 KB |
90_cycle_like_0 | AC | 913 ms | 41600 KB |
90_cycle_like_1 | AC | 902 ms | 41344 KB |
90_cycle_like_2 | AC | 881 ms | 40448 KB |
90_cycle_like_3 | AC | 910 ms | 42112 KB |
90_cycle_like_4 | AC | 909 ms | 41856 KB |
91_cycle_like_dense_0 | AC | 1687 ms | 36480 KB |
91_cycle_like_dense_1 | AC | 1023 ms | 40960 KB |
91_cycle_like_dense_2 | AC | 950 ms | 40960 KB |
91_cycle_like_dense_3 | AC | 937 ms | 40832 KB |
91_cycle_like_dense_4 | AC | 1599 ms | 37504 KB |
91_cycle_like_dense_5 | AC | 1194 ms | 39808 KB |
91_cycle_like_dense_6 | AC | 1627 ms | 38656 KB |
91_cycle_like_dense_7 | AC | 1187 ms | 39040 KB |
91_cycle_like_dense_8 | AC | 1263 ms | 39552 KB |
91_cycle_like_dense_9 | AC | 1348 ms | 38912 KB |
99_ng_max_dense_0 | AC | 113 ms | 1920 KB |
99_ng_max_odd_prime_0 | AC | 16 ms | 1920 KB |
99_ng_max_odd_prime_dense_0 | AC | 82 ms | 1920 KB |
99_ng_max_odd_prime_dense_1 | AC | 64 ms | 1920 KB |
99_ng_max_odd_prime_dense_2 | AC | 102 ms | 1920 KB |
99_ng_max_odd_prime_dense_3 | AC | 90 ms | 1920 KB |
99_ng_max_odd_prime_dense_4 | AC | 54 ms | 1920 KB |
99_ng_max_prime_0 | AC | 16 ms | 1920 KB |
99_ok_max_0 | AC | 774 ms | 41472 KB |