#include <bits/stdc++.h>
#define DIMN 400010
using namespace std;
int tt[DIMN];
int sz[DIMN] , opt[DIMN];
int n , m , where;
pair <int , int> mch[DIMN];
vector <int> s;
vector <int> v;
int root (int x){
while (tt[x] != x)
x = tt[x];
return x;
}
inline void unite (int x, int y){
int radx = x, rady = y;
if (sz[radx] < sz[rady])
swap (radx,rady);
s.push_back(rady); /// stiva pt undo
sz[radx] += sz[rady];
tt[rady] = radx;
}
inline int unite_init (int x , int y){
int radx = root(x) , radnx , rady = root(y) , radny;
if (radx == rady)
return 0;
radnx = root(n + x);
radny = root(n + y);
unite(radx , radny);
unite(rady , radnx);
return 1;
}
void solve (int st , int dr , int l , int r){
int mid = (st + dr)/2 , i , poz , x , y , init , init2;
if (mid <= where){
if (mid + 1 <= dr)
solve(mid + 1 , dr , l , r);
return;
}
init = s.size();
for (i = min(dr , m) ; i >= mid ; i--){
x = mch[i].first;
y = mch[i].second;
if (!unite_init(x , y))
break;
//v.push_back(i);
}
if (i >= mid){ /// nu se poate cu toate
where = i;
while (s.size() != init){
y = s.back();
s.pop_back();
sz[tt[y]] -= sz[y];
tt[y] = y;
}
/// te duci doar in dreapta
if (mid + 1 <= dr)
solve(mid + 1 , dr , l , r);
return;
}
init2 = s.size();
poz = l;
for (i = l + 1 ; i <= r && i < mid ; i++){
x = mch[i].first;
y = mch[i].second;
if (!unite_init(x , y))
break;
poz = i;
}
opt[mid] = poz;
while (s.size() != init2){
y = s.back();
s.pop_back();
sz[tt[y]] -= sz[y];
tt[y] = y;
}
if (st <= mid - 1)
solve (st , mid - 1 , l , poz);
while (s.size() != init){
y = s.back();
s.pop_back();
sz[tt[y]] -= sz[y];
tt[y] = y;
}
if (mid + 1 <= dr){
for (i = l + 1 ; i <= poz ; i++){
x = mch[i].first;
y = mch[i].second;
unite_init (x , y);
//v.push_back(i);
}
solve(mid + 1 , dr , poz , r);
while (s.size() != init){
y = s.back();
s.pop_back();
sz[tt[y]] -= sz[y];
tt[y] = y;
}
}
/// convine sa te duci mai intai in dreapta, pastrezi tot ce ai adaugat
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int q , i , l , r;
fscanf (fin,"%d%d%d",&n,&m,&q);
for (i = 1 ; i <= m ; i++){
fscanf (fin,"%d%d",&mch[i].first,&mch[i].second);
}
/// opt se calculeaza intre 1 si M + 1
for (i = 1 ; i <= 2 * n ; i++){
tt[i] = i;
sz[i] = 1;
}
where = 0;
solve (1 , m + 1 , 0 , m); /// te asiguri ca dreapta nu cauzeaza ciclu impar
for (;q;q--){
fscanf (fin,"%d%d",&l,&r);
if (opt[r + 1] >= l - 1 && r + 1 > where)
fprintf (fout,"NO\n");
else fprintf (fout,"YES\n");
}
return 0;
}
Compilation message
Joker.cpp: In function 'void solve(int, int, int, int)':
Joker.cpp:69:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
69 | while (s.size() != init){
| ~~~~~~~~~^~~~~~~
Joker.cpp:105:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
105 | while (s.size() != init2){
| ~~~~~~~~~^~~~~~~~
Joker.cpp:117:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
117 | while (s.size() != init){
| ~~~~~~~~~^~~~~~~
Joker.cpp:138:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
138 | while (s.size() != init){
| ~~~~~~~~~^~~~~~~
Joker.cpp: In function 'int main()':
Joker.cpp:156:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
156 | fscanf (fin,"%d%d%d",&n,&m,&q);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:158:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
158 | fscanf (fin,"%d%d",&mch[i].first,&mch[i].second);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:171:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
171 | fscanf (fin,"%d%d",&l,&r);
| ~~~~~~~^~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
300 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
396 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
300 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
396 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
296 KB |
Output is correct |
29 |
Correct |
2 ms |
308 KB |
Output is correct |
30 |
Correct |
3 ms |
444 KB |
Output is correct |
31 |
Correct |
3 ms |
356 KB |
Output is correct |
32 |
Correct |
3 ms |
332 KB |
Output is correct |
33 |
Correct |
2 ms |
332 KB |
Output is correct |
34 |
Correct |
3 ms |
348 KB |
Output is correct |
35 |
Correct |
3 ms |
332 KB |
Output is correct |
36 |
Correct |
2 ms |
312 KB |
Output is correct |
37 |
Correct |
3 ms |
332 KB |
Output is correct |
38 |
Correct |
3 ms |
332 KB |
Output is correct |
39 |
Correct |
3 ms |
332 KB |
Output is correct |
40 |
Correct |
3 ms |
332 KB |
Output is correct |
41 |
Correct |
2 ms |
332 KB |
Output is correct |
42 |
Correct |
3 ms |
332 KB |
Output is correct |
43 |
Correct |
4 ms |
332 KB |
Output is correct |
44 |
Correct |
4 ms |
332 KB |
Output is correct |
45 |
Correct |
3 ms |
332 KB |
Output is correct |
46 |
Correct |
3 ms |
332 KB |
Output is correct |
47 |
Correct |
3 ms |
332 KB |
Output is correct |
48 |
Correct |
4 ms |
400 KB |
Output is correct |
49 |
Correct |
4 ms |
332 KB |
Output is correct |
50 |
Correct |
5 ms |
332 KB |
Output is correct |
51 |
Correct |
4 ms |
332 KB |
Output is correct |
52 |
Correct |
4 ms |
312 KB |
Output is correct |
53 |
Correct |
3 ms |
356 KB |
Output is correct |
54 |
Correct |
3 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
245 ms |
6148 KB |
Output is correct |
4 |
Correct |
852 ms |
8088 KB |
Output is correct |
5 |
Correct |
357 ms |
6848 KB |
Output is correct |
6 |
Correct |
335 ms |
5260 KB |
Output is correct |
7 |
Correct |
270 ms |
5248 KB |
Output is correct |
8 |
Execution timed out |
2050 ms |
3956 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
300 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
396 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
296 KB |
Output is correct |
29 |
Correct |
245 ms |
6148 KB |
Output is correct |
30 |
Correct |
852 ms |
8088 KB |
Output is correct |
31 |
Correct |
357 ms |
6848 KB |
Output is correct |
32 |
Correct |
335 ms |
5260 KB |
Output is correct |
33 |
Correct |
270 ms |
5248 KB |
Output is correct |
34 |
Execution timed out |
2050 ms |
3956 KB |
Time limit exceeded |
35 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
300 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
396 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
296 KB |
Output is correct |
29 |
Correct |
2 ms |
308 KB |
Output is correct |
30 |
Correct |
3 ms |
444 KB |
Output is correct |
31 |
Correct |
3 ms |
356 KB |
Output is correct |
32 |
Correct |
3 ms |
332 KB |
Output is correct |
33 |
Correct |
2 ms |
332 KB |
Output is correct |
34 |
Correct |
3 ms |
348 KB |
Output is correct |
35 |
Correct |
3 ms |
332 KB |
Output is correct |
36 |
Correct |
2 ms |
312 KB |
Output is correct |
37 |
Correct |
3 ms |
332 KB |
Output is correct |
38 |
Correct |
3 ms |
332 KB |
Output is correct |
39 |
Correct |
3 ms |
332 KB |
Output is correct |
40 |
Correct |
3 ms |
332 KB |
Output is correct |
41 |
Correct |
2 ms |
332 KB |
Output is correct |
42 |
Correct |
3 ms |
332 KB |
Output is correct |
43 |
Correct |
4 ms |
332 KB |
Output is correct |
44 |
Correct |
4 ms |
332 KB |
Output is correct |
45 |
Correct |
3 ms |
332 KB |
Output is correct |
46 |
Correct |
3 ms |
332 KB |
Output is correct |
47 |
Correct |
3 ms |
332 KB |
Output is correct |
48 |
Correct |
4 ms |
400 KB |
Output is correct |
49 |
Correct |
4 ms |
332 KB |
Output is correct |
50 |
Correct |
5 ms |
332 KB |
Output is correct |
51 |
Correct |
4 ms |
332 KB |
Output is correct |
52 |
Correct |
4 ms |
312 KB |
Output is correct |
53 |
Correct |
3 ms |
356 KB |
Output is correct |
54 |
Correct |
3 ms |
332 KB |
Output is correct |
55 |
Correct |
188 ms |
5244 KB |
Output is correct |
56 |
Correct |
549 ms |
8028 KB |
Output is correct |
57 |
Correct |
199 ms |
7544 KB |
Output is correct |
58 |
Correct |
219 ms |
5340 KB |
Output is correct |
59 |
Execution timed out |
2049 ms |
5132 KB |
Time limit exceeded |
60 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
300 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
396 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
296 KB |
Output is correct |
29 |
Correct |
2 ms |
308 KB |
Output is correct |
30 |
Correct |
3 ms |
444 KB |
Output is correct |
31 |
Correct |
3 ms |
356 KB |
Output is correct |
32 |
Correct |
3 ms |
332 KB |
Output is correct |
33 |
Correct |
2 ms |
332 KB |
Output is correct |
34 |
Correct |
3 ms |
348 KB |
Output is correct |
35 |
Correct |
3 ms |
332 KB |
Output is correct |
36 |
Correct |
2 ms |
312 KB |
Output is correct |
37 |
Correct |
3 ms |
332 KB |
Output is correct |
38 |
Correct |
3 ms |
332 KB |
Output is correct |
39 |
Correct |
3 ms |
332 KB |
Output is correct |
40 |
Correct |
3 ms |
332 KB |
Output is correct |
41 |
Correct |
2 ms |
332 KB |
Output is correct |
42 |
Correct |
3 ms |
332 KB |
Output is correct |
43 |
Correct |
4 ms |
332 KB |
Output is correct |
44 |
Correct |
4 ms |
332 KB |
Output is correct |
45 |
Correct |
3 ms |
332 KB |
Output is correct |
46 |
Correct |
3 ms |
332 KB |
Output is correct |
47 |
Correct |
3 ms |
332 KB |
Output is correct |
48 |
Correct |
4 ms |
400 KB |
Output is correct |
49 |
Correct |
4 ms |
332 KB |
Output is correct |
50 |
Correct |
5 ms |
332 KB |
Output is correct |
51 |
Correct |
4 ms |
332 KB |
Output is correct |
52 |
Correct |
4 ms |
312 KB |
Output is correct |
53 |
Correct |
3 ms |
356 KB |
Output is correct |
54 |
Correct |
3 ms |
332 KB |
Output is correct |
55 |
Correct |
245 ms |
6148 KB |
Output is correct |
56 |
Correct |
852 ms |
8088 KB |
Output is correct |
57 |
Correct |
357 ms |
6848 KB |
Output is correct |
58 |
Correct |
335 ms |
5260 KB |
Output is correct |
59 |
Correct |
270 ms |
5248 KB |
Output is correct |
60 |
Execution timed out |
2050 ms |
3956 KB |
Time limit exceeded |
61 |
Halted |
0 ms |
0 KB |
- |