# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
638575 | 2022-09-06T12:14:01 Z | morasha3 | Alternating Heights (CCO22_day1problem1) | C++17 | 1000 ms | 4348 KB |
#include <bits/stdc++.h> using namespace std; typedef int ll; typedef double ld; const ll mod=1e9+7; #define endl '\n' bool dfs(vector<vector<int>>& v) { int n = v.size(); vector<int> deg(n); for (int a = 0; a < n; a++) for (int b : v[a]) deg[b]++; vector<int> q; q.reserve(n); for (int i = 0; i < n; i++) if (deg[i] == 0) q.push_back(i); for (int rep = 0; rep < q.size(); rep++) { int c = q[rep]; for (auto nxt : v[c]) { deg[nxt]--; if (deg[nxt] == 0) q.push_back(nxt); } } return n>q.size(); } int32_t main() { //freopen("jumping.in","r",stdin); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n,k,q; cin>>n>>k>>q; ll arr[n]; for(int i=0; i<n; i++) cin>>arr[i]; ll m[n]; for(int i=0; i<n; i++) m[i]=i; for(int h:{0,1}) { for(int i=h; i<n; i+=2) { ll r=i+1,c=0; while(r<n) { vector<vector<ll>>adj(k); for(int j=i; j<r; j++) { if (j % 2 == i % 2) adj[arr[j]-1].push_back(arr[j + 1]-1); else adj[arr[j + 1]-1].push_back(arr[j]-1); } if(dfs(adj)) break; r++; } m[i]=r-1; } } while(q--) { ll a,b; cin>>a>>b; a--,b--; if(m[a]>=b) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 166 ms | 3428 KB | Output is correct |
2 | Correct | 164 ms | 3320 KB | Output is correct |
3 | Correct | 176 ms | 3364 KB | Output is correct |
4 | Correct | 128 ms | 3240 KB | Output is correct |
5 | Correct | 149 ms | 3368 KB | Output is correct |
6 | Correct | 167 ms | 3220 KB | Output is correct |
7 | Correct | 171 ms | 3268 KB | Output is correct |
8 | Correct | 191 ms | 3324 KB | Output is correct |
9 | Correct | 731 ms | 3468 KB | Output is correct |
10 | Execution timed out | 1089 ms | 340 KB | Time limit exceeded |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 156 ms | 3312 KB | Output is correct |
2 | Correct | 167 ms | 3336 KB | Output is correct |
3 | Correct | 150 ms | 3256 KB | Output is correct |
4 | Correct | 128 ms | 4348 KB | Output is correct |
5 | Correct | 144 ms | 3532 KB | Output is correct |
6 | Correct | 156 ms | 3336 KB | Output is correct |
7 | Correct | 175 ms | 3332 KB | Output is correct |
8 | Correct | 156 ms | 3348 KB | Output is correct |
9 | Correct | 219 ms | 3728 KB | Output is correct |
10 | Correct | 462 ms | 4284 KB | Output is correct |
11 | Correct | 438 ms | 4300 KB | Output is correct |
12 | Correct | 0 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Execution timed out | 1073 ms | 340 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 166 ms | 3428 KB | Output is correct |
2 | Correct | 164 ms | 3320 KB | Output is correct |
3 | Correct | 176 ms | 3364 KB | Output is correct |
4 | Correct | 128 ms | 3240 KB | Output is correct |
5 | Correct | 149 ms | 3368 KB | Output is correct |
6 | Correct | 167 ms | 3220 KB | Output is correct |
7 | Correct | 171 ms | 3268 KB | Output is correct |
8 | Correct | 191 ms | 3324 KB | Output is correct |
9 | Correct | 731 ms | 3468 KB | Output is correct |
10 | Execution timed out | 1089 ms | 340 KB | Time limit exceeded |
11 | Halted | 0 ms | 0 KB | - |