| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 256173 |
2020-08-02T10:48:59 Z |
구재현(#5035) |
Joker (BOI20_joker) |
C++17 |
|
2000 ms |
13464 KB |
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 400005;
struct event{
int *p;
int v;
};
int n, m, q;
pi a[MAXN];
void rollback(vector<event> &E){
reverse(all(E));
for(auto &i : E){
*i.p = i.v;
}
E.clear();
}
struct btracker{
int pa[MAXN], rk[MAXN];
int is_cycle;
void init(int n){
iota(pa, pa + n + 1, 0);
memset(rk, 0, sizeof(rk));
is_cycle = 0;
}
int find(int x){
return pa[x] == x ? x : find(pa[x]);
}
bool uni(int p, int q){
p = find(p);
q = find(q);
if(p == q) return 0;
if(rk[p] > rk[q]) swap(p, q);
pa[p] = q;
if(rk[p] == rk[q]) rk[q]++;
return 1;
}
bool uni(int p, int q, vector<event> &snap){
p = find(p);
q = find(q);
if(p == q) return 0;
if(rk[p] > rk[q]) swap(p, q);
snap.push_back((event){&pa[p], pa[p]});
pa[p] = q;
if(rk[p] == rk[q]){
snap.push_back((event){&rk[q], rk[q]});
rk[q]++;
}
return 1;
}
void add_edge(int x, int y){
uni(x, y + n);
uni(y, x + n);
if(find(x) == find(x + n)) is_cycle = 1;
}
void add_edge(int x, int y, vector<event> &snap){
uni(x, y + n, snap);
uni(y, x + n, snap);
if(find(x) == find(x + n)){
snap.push_back((event){&is_cycle, is_cycle});
is_cycle = 1;
}
}
}disj;
int dap[MAXN];
void solve(int s, int e, int ps, int pe){
}
int main(){
scanf("%d %d %d",&n,&m,&q);
for(int i=1; i<=m; i++){
scanf("%d %d",&a[i].first,&a[i].second);
a[i + m] = a[i];
}
disj.init(n+n);
int stpos = -1;
for(int i=m; i; i--){
disj.add_edge(a[i].first, a[i].second);
if(disj.is_cycle){
stpos = i + 1;
break;
}
}
if(disj.is_cycle == 0){
while(q--) puts("NO");
return 0;
}
disj.init(n+n);
for(int i=stpos; i<=m+1; i++){
vector<event> v;
dap[i] = 2 * m;
for(int j=i; j<=2*m; j++){
disj.add_edge(a[j].first, a[j].second, v);
if(disj.is_cycle){
dap[i] = j - 1;
break;
}
}
rollback(v);
}
//solve(stpos, m + 1, m + 1, 2 * m);
while(q--){
int x, y; scanf("%d %d",&x,&y);
if(y + 1 < stpos) puts("YES");
else puts(dap[y + 1] < x + m - 1? "YES" : "NO");
}
}
Compilation message
Joker.cpp: In function 'int main()':
Joker.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&n,&m,&q);
~~~~~^~~~~~~~~~~~~~~~~~~~~
Joker.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&a[i].first,&a[i].second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:113:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x, y; scanf("%d %d",&x,&y);
~~~~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 16 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 17 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 18 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 19 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 20 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 21 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 22 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 23 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 24 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 25 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 26 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 27 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 28 |
Correct |
3 ms |
1920 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 16 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 17 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 18 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 19 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 20 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 21 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 22 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 23 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 24 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 25 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 26 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 27 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 28 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 29 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 30 |
Correct |
53 ms |
2048 KB |
Output is correct |
| 31 |
Correct |
43 ms |
2048 KB |
Output is correct |
| 32 |
Correct |
20 ms |
2064 KB |
Output is correct |
| 33 |
Correct |
7 ms |
2048 KB |
Output is correct |
| 34 |
Correct |
55 ms |
2048 KB |
Output is correct |
| 35 |
Correct |
69 ms |
2048 KB |
Output is correct |
| 36 |
Correct |
47 ms |
2048 KB |
Output is correct |
| 37 |
Correct |
108 ms |
2048 KB |
Output is correct |
| 38 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 39 |
Correct |
10 ms |
2060 KB |
Output is correct |
| 40 |
Correct |
29 ms |
2048 KB |
Output is correct |
| 41 |
Correct |
21 ms |
2048 KB |
Output is correct |
| 42 |
Correct |
29 ms |
2048 KB |
Output is correct |
| 43 |
Correct |
31 ms |
2048 KB |
Output is correct |
| 44 |
Correct |
38 ms |
2048 KB |
Output is correct |
| 45 |
Correct |
40 ms |
2168 KB |
Output is correct |
| 46 |
Correct |
63 ms |
2048 KB |
Output is correct |
| 47 |
Correct |
31 ms |
2048 KB |
Output is correct |
| 48 |
Correct |
34 ms |
2176 KB |
Output is correct |
| 49 |
Correct |
50 ms |
2048 KB |
Output is correct |
| 50 |
Correct |
52 ms |
2048 KB |
Output is correct |
| 51 |
Correct |
44 ms |
2048 KB |
Output is correct |
| 52 |
Correct |
45 ms |
2048 KB |
Output is correct |
| 53 |
Correct |
56 ms |
2048 KB |
Output is correct |
| 54 |
Correct |
65 ms |
2048 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 3 |
Execution timed out |
2092 ms |
13420 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 16 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 17 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 18 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 19 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 20 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 21 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 22 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 23 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 24 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 25 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 26 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 27 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 28 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 29 |
Execution timed out |
2092 ms |
13420 KB |
Time limit exceeded |
| 30 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 16 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 17 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 18 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 19 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 20 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 21 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 22 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 23 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 24 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 25 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 26 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 27 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 28 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 29 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 30 |
Correct |
53 ms |
2048 KB |
Output is correct |
| 31 |
Correct |
43 ms |
2048 KB |
Output is correct |
| 32 |
Correct |
20 ms |
2064 KB |
Output is correct |
| 33 |
Correct |
7 ms |
2048 KB |
Output is correct |
| 34 |
Correct |
55 ms |
2048 KB |
Output is correct |
| 35 |
Correct |
69 ms |
2048 KB |
Output is correct |
| 36 |
Correct |
47 ms |
2048 KB |
Output is correct |
| 37 |
Correct |
108 ms |
2048 KB |
Output is correct |
| 38 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 39 |
Correct |
10 ms |
2060 KB |
Output is correct |
| 40 |
Correct |
29 ms |
2048 KB |
Output is correct |
| 41 |
Correct |
21 ms |
2048 KB |
Output is correct |
| 42 |
Correct |
29 ms |
2048 KB |
Output is correct |
| 43 |
Correct |
31 ms |
2048 KB |
Output is correct |
| 44 |
Correct |
38 ms |
2048 KB |
Output is correct |
| 45 |
Correct |
40 ms |
2168 KB |
Output is correct |
| 46 |
Correct |
63 ms |
2048 KB |
Output is correct |
| 47 |
Correct |
31 ms |
2048 KB |
Output is correct |
| 48 |
Correct |
34 ms |
2176 KB |
Output is correct |
| 49 |
Correct |
50 ms |
2048 KB |
Output is correct |
| 50 |
Correct |
52 ms |
2048 KB |
Output is correct |
| 51 |
Correct |
44 ms |
2048 KB |
Output is correct |
| 52 |
Correct |
45 ms |
2048 KB |
Output is correct |
| 53 |
Correct |
56 ms |
2048 KB |
Output is correct |
| 54 |
Correct |
65 ms |
2048 KB |
Output is correct |
| 55 |
Execution timed out |
2064 ms |
13464 KB |
Time limit exceeded |
| 56 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 5 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1920 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 14 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 15 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 16 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 17 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 18 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 19 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 20 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 21 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 22 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 23 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 24 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 25 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 26 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 27 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 28 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 29 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 30 |
Correct |
53 ms |
2048 KB |
Output is correct |
| 31 |
Correct |
43 ms |
2048 KB |
Output is correct |
| 32 |
Correct |
20 ms |
2064 KB |
Output is correct |
| 33 |
Correct |
7 ms |
2048 KB |
Output is correct |
| 34 |
Correct |
55 ms |
2048 KB |
Output is correct |
| 35 |
Correct |
69 ms |
2048 KB |
Output is correct |
| 36 |
Correct |
47 ms |
2048 KB |
Output is correct |
| 37 |
Correct |
108 ms |
2048 KB |
Output is correct |
| 38 |
Correct |
3 ms |
1920 KB |
Output is correct |
| 39 |
Correct |
10 ms |
2060 KB |
Output is correct |
| 40 |
Correct |
29 ms |
2048 KB |
Output is correct |
| 41 |
Correct |
21 ms |
2048 KB |
Output is correct |
| 42 |
Correct |
29 ms |
2048 KB |
Output is correct |
| 43 |
Correct |
31 ms |
2048 KB |
Output is correct |
| 44 |
Correct |
38 ms |
2048 KB |
Output is correct |
| 45 |
Correct |
40 ms |
2168 KB |
Output is correct |
| 46 |
Correct |
63 ms |
2048 KB |
Output is correct |
| 47 |
Correct |
31 ms |
2048 KB |
Output is correct |
| 48 |
Correct |
34 ms |
2176 KB |
Output is correct |
| 49 |
Correct |
50 ms |
2048 KB |
Output is correct |
| 50 |
Correct |
52 ms |
2048 KB |
Output is correct |
| 51 |
Correct |
44 ms |
2048 KB |
Output is correct |
| 52 |
Correct |
45 ms |
2048 KB |
Output is correct |
| 53 |
Correct |
56 ms |
2048 KB |
Output is correct |
| 54 |
Correct |
65 ms |
2048 KB |
Output is correct |
| 55 |
Execution timed out |
2092 ms |
13420 KB |
Time limit exceeded |
| 56 |
Halted |
0 ms |
0 KB |
- |
