| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 414447 |
2021-05-30T12:43:41 Z |
Ruxandra985 |
Joker (BOI20_joker) |
C++14 |
|
2000 ms |
24356 KB |
#include <bits/stdc++.h>
#define DIMN 400010
using namespace std;
int tt[DIMN];
int sz[DIMN] , opt[DIMN];
int n , m;
pair <int , int> mch[DIMN];
vector <pair <int , int> > s;
int root (int x){
while (tt[x] != x)
x = tt[x];
return x;
}
void unite (int x, int y){
int radx = root(x), rady = root(y);
//printf ("add %d %d\n" , x , y);
if (sz[radx] < sz[rady])
swap (radx,rady);
s.push_back(make_pair(radx,rady)); /// stiva pt undo
sz[radx] += sz[rady];
tt[rady] = radx;
}
void undo (){
int x = s.back().first, y = s.back().second;
s.pop_back();
//printf ("undo\n");
sz[x] -= sz[y];
tt[y] = y;
}
void solve (int st , int dr , int l , int r , int needs){
int mid = (st + dr)/2 , i , poz , x , y , m2;
if (needs){
for (i = dr ; i >= mid ; i--){
x = mch[i].first;
y = mch[i].second;
unite (x , y + n);
unite (y , x + n);
}
}
l = max(l , 1);
poz = 0;
for (i = l ; i <= r && i < mid ; i++){
x = mch[i].first;
y = mch[i].second;
if (root(x) == root(y) || root(y + n) == root(x + n)){
break;
}
unite (x , y + n);
unite (y , x + n);
poz = i;
}
opt[mid] = poz;
for (i = l ; i <= poz ; i++){
undo();
undo();
}
if (st <= mid - 1)
solve (st , mid - 1 , l , poz , 1);
if (mid + 1 <= dr){
m2 = (dr + mid + 1) / 2;
for (i = mid ; i <= dr; i++){
undo();
undo();
}
for (i = l ; i < poz ; i++){
x = mch[i].first;
y = mch[i].second;
unite (x , y + n);
unite (y , x + n);
}
solve(mid + 1 , dr , poz , r , 1);
}
/// convine sa te duci mai intai in dreapta, pastrezi tot ce ai adaugat
if (st == dr){
undo();
undo();
}
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int q , i , x , y , poz , j , 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;
}
for (i = m ; i ; i--){
x = mch[i].first;
y = mch[i].second;
if (root(x) == root(y) || root(y + n) == root(x + n)){
break;
}
unite (x , y + n);
unite (y , x + n);
}
poz = i + 1;
for (j = i + 1 ; j <= m ; j++){
undo();
undo();
}
int where = poz;
solve (poz , m , 1 , m , 1); /// te asiguri ca dreapta nu cauzeaza ciclu impar
//printf ("-----------------\n");
for (i = 1 ; i <= m ; i++){
x = mch[i].first;
y = mch[i].second;
if (root(x) == root(y) || root(y + n) == root(x + n)){
break;
}
unite (x , y + n);
unite (y , x + n);
}
poz = i - 1;
opt[m + 1] = poz;
for (j = i - 1 ; j ; j--){
undo();
undo();
}
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, int)':
Joker.cpp:38:47: warning: variable 'm2' set but not used [-Wunused-but-set-variable]
38 | int mid = (st + dr)/2 , i , poz , x , y , m2;
| ^~
Joker.cpp: In function 'int main()':
Joker.cpp:112:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | fscanf (fin,"%d%d%d",&n,&m,&q);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:114:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | fscanf (fin,"%d%d",&mch[i].first,&mch[i].second);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:169:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
169 | fscanf (fin,"%d%d",&l,&r);
| ~~~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 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 |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| 6 |
Correct |
1 ms |
300 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 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 |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| 6 |
Correct |
1 ms |
300 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
160 ms |
10860 KB |
Output is correct |
| 4 |
Execution timed out |
2079 ms |
24356 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 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 |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| 6 |
Correct |
1 ms |
300 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 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 |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| 6 |
Correct |
1 ms |
300 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 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 |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
300 KB |
Output is correct |
| 6 |
Correct |
1 ms |
300 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
