This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define DIM 400010
using namespace std;
int fth[DIM],Size[DIM],dp[DIM];
pair <int,int> mch[DIM];
deque <pair<int,int> > s;
int n,m,q,x,y,i;
int get_rad (int x){
while (fth[x] != x)
x = fth[x];
return x;
}
int uneste (int x, int y, int &cnt){
int radx = get_rad (x), rady = get_rad (y);
if (radx == rady)
return 0;
cnt++;
if (Size[radx] < Size[rady])
swap (radx,rady);
s.push_back(make_pair(radx,rady));
Size[radx] += Size[rady];
fth[rady] = radx;
return 1;
}
void undo(){
int x = s.back().first, y = s.back().second;
s.pop_back();
Size[x] -= Size[y];
fth[y] = y;
}
void solve (int st, int dr, int opt_st, int opt_dr){
if (st > dr)
return;
int mid = (st+dr)>>1, opt_mid;
/// adaug tot pana la mid
int ok = 0;
int cnt = 0; /// de cate ori fac unirile efective
for (int i=max(1,st-1);i<mid;i++){
int x = mch[i].first, y = mch[i].second;
if (!uneste(x,y,cnt)){
ok = 1;
break;
} else undo(), cnt--;
uneste (x,y+n,cnt);
uneste (x+n,y,cnt);
}
if (ok){ /// se strica proprietatea de bipartit pana sa ajung la mid
dp[mid] = m+1;
opt_mid = m+1;
} else {
for (opt_mid = min(m,opt_dr); opt_mid >= mid ; opt_mid--){
/// adaug muchia asta si vad daca se pastreaza propr de bipartit
int x = mch[opt_mid].first, y = mch[opt_mid].second;
if (!uneste(x,y,cnt)){
break;
} else undo(),cnt--;
uneste (x,y+n,cnt); /// muchiile astea vin ca la 2sat
uneste (x+n,y,cnt);
}
dp[mid] = opt_mid;
}
/// trb sa construiesc padurile special pt urmatorul apel
/// dau undo la toate si mai adaug dupa de la opt_mid la opt_dr
for (int i=1;i<=cnt;i++)
undo();
int val = 0;
for (int i=opt_dr;i>opt_mid;i--){
int x = mch[i].first, y = mch[i].second;
uneste (x,y+n,val);
uneste (x+n,y,val);
}
solve (st,mid-1,opt_st,opt_mid);
for (int i=1;i<=val;i++)
undo();
int val2 = 0;
for (int i=st;i<mid;i++){
int x = mch[i].first, y = mch[i].second;
uneste (x,y+n,val2);
uneste (x+n,y,val2);
}
solve (mid+1,dr,opt_mid,opt_dr);
for (int i=1;i<=val2;i++)
undo();
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>m>>q;
for (i=1;i<=m;i++)
cin>>mch[i].first>>mch[i].second;
for (i=1;i<=2*n;i++)
fth[i] = i, Size[i] = 1;
solve (1,m,1,m+1);
for (;q--;){
cin>>x>>y;
if (y >= dp[x])
cout<<"NO\n";
else cout<<"YES\n";
/*if (dp[x] == m+1 || dp[x] > y)
cout<<"YES\n";
else cout<<"NO\n";*/
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |