| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1037446 |
2024-07-28T22:25:46 Z |
wood |
Joker (BOI20_joker) |
C++17 |
|
2000 ms |
20672 KB |
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> p32;
typedef vector<p32> vp32;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
int main(){
int n,m,q; cin>>n>>m>>q;
vp32 adj[n];
for(int i = 0; i<m; i++){
int a,b; cin>>a>>b;
a--; b--;
adj[a].eb(b,i+1);
adj[b].eb(a,i+1);
}
vp32 querries[200];
for(int j = 0; j<q; j++){
int l,r; cin>>l>>r;
querries[l-1].eb(r,j);
}
int res[q];
memset(res,0,sizeof res);
for(int l = 0; l<200; l++){
sort(querries[l].begin(),querries[l].end());
int left = -1, right = querries[l].size();
while(right-left>1){
int m = (right+left)/2;
int parent[n];
int depth[n];
memset(parent,0,sizeof parent);
memset(depth,0,sizeof depth);
stack<int> qu;
for(int i = 0; i<n; i++){
if(!parent[i]){
parent[i] = i+1;
qu.push(i);
while(!qu.empty()){
int x = qu.top();
depth[x] = depth[parent[x]-1]+1;
qu.pop();
for(p32 tt : adj[x]){
if(tt.se<l+1||tt.se>querries[l][m].first){
if(depth[tt.fi]&&parent[x]-1!=tt.fi&&((depth[x]-depth[tt.fi]+1)&1)) goto found;
if(parent[tt.fi]==0){
parent[tt.fi] = x+1;
qu.push(tt.fi);
}
}
}
}
}
}
right = m;
continue;
found:
left = m;
}
for(int i = 0; i<=left; i++){
res[querries[l][i].se] = true;
}
}
for(bool x : res) cout<<(x ? "YES\n" : "NO\n");
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
1 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
364 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
0 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
348 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Correct |
1 ms |
348 KB |
Output is correct |
| 26 |
Correct |
1 ms |
348 KB |
Output is correct |
| 27 |
Correct |
1 ms |
348 KB |
Output is correct |
| 28 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
1 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
364 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
0 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
348 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Correct |
1 ms |
348 KB |
Output is correct |
| 26 |
Correct |
1 ms |
348 KB |
Output is correct |
| 27 |
Correct |
1 ms |
348 KB |
Output is correct |
| 28 |
Correct |
1 ms |
348 KB |
Output is correct |
| 29 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 30 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
186 ms |
12768 KB |
Output is correct |
| 4 |
Correct |
260 ms |
20264 KB |
Output is correct |
| 5 |
Correct |
208 ms |
20420 KB |
Output is correct |
| 6 |
Correct |
211 ms |
16960 KB |
Output is correct |
| 7 |
Correct |
249 ms |
16832 KB |
Output is correct |
| 8 |
Correct |
191 ms |
14652 KB |
Output is correct |
| 9 |
Correct |
221 ms |
16316 KB |
Output is correct |
| 10 |
Correct |
213 ms |
20480 KB |
Output is correct |
| 11 |
Correct |
221 ms |
16648 KB |
Output is correct |
| 12 |
Correct |
261 ms |
19776 KB |
Output is correct |
| 13 |
Correct |
181 ms |
13244 KB |
Output is correct |
| 14 |
Correct |
234 ms |
15040 KB |
Output is correct |
| 15 |
Correct |
311 ms |
18444 KB |
Output is correct |
| 16 |
Correct |
259 ms |
20672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
1 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
364 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
0 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
348 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Correct |
1 ms |
348 KB |
Output is correct |
| 26 |
Correct |
1 ms |
348 KB |
Output is correct |
| 27 |
Correct |
1 ms |
348 KB |
Output is correct |
| 28 |
Correct |
1 ms |
348 KB |
Output is correct |
| 29 |
Correct |
186 ms |
12768 KB |
Output is correct |
| 30 |
Correct |
260 ms |
20264 KB |
Output is correct |
| 31 |
Correct |
208 ms |
20420 KB |
Output is correct |
| 32 |
Correct |
211 ms |
16960 KB |
Output is correct |
| 33 |
Correct |
249 ms |
16832 KB |
Output is correct |
| 34 |
Correct |
191 ms |
14652 KB |
Output is correct |
| 35 |
Correct |
221 ms |
16316 KB |
Output is correct |
| 36 |
Correct |
213 ms |
20480 KB |
Output is correct |
| 37 |
Correct |
221 ms |
16648 KB |
Output is correct |
| 38 |
Correct |
261 ms |
19776 KB |
Output is correct |
| 39 |
Correct |
181 ms |
13244 KB |
Output is correct |
| 40 |
Correct |
234 ms |
15040 KB |
Output is correct |
| 41 |
Correct |
311 ms |
18444 KB |
Output is correct |
| 42 |
Correct |
259 ms |
20672 KB |
Output is correct |
| 43 |
Execution timed out |
2069 ms |
15444 KB |
Time limit exceeded |
| 44 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
1 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
364 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
0 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
348 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Correct |
1 ms |
348 KB |
Output is correct |
| 26 |
Correct |
1 ms |
348 KB |
Output is correct |
| 27 |
Correct |
1 ms |
348 KB |
Output is correct |
| 28 |
Correct |
1 ms |
348 KB |
Output is correct |
| 29 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 30 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
1 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
364 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
0 ms |
348 KB |
Output is correct |
| 22 |
Correct |
1 ms |
348 KB |
Output is correct |
| 23 |
Correct |
1 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Correct |
1 ms |
348 KB |
Output is correct |
| 26 |
Correct |
1 ms |
348 KB |
Output is correct |
| 27 |
Correct |
1 ms |
348 KB |
Output is correct |
| 28 |
Correct |
1 ms |
348 KB |
Output is correct |
| 29 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 30 |
Halted |
0 ms |
0 KB |
- |
