| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 837969 | 1075508020060209tc | Joker (BOI20_joker) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int n;int m;int Q;
int ar[400005];
int br[400005];
int uf[200005];
int isbip;
int sz[200005];
int ufv[200005];
stack<int>stk;
stack<int>stkv;
stack<int>stkbp;
int fin(int x){
if(uf[x]==x){return x;}
int v=finv(uf[x]);
ufv[x]=v;
uf[x]=fin(uf[x]);
return uf[x];
}
int finv(int x){
if(uf[x]==x){return 0;}
return (ufv[x]+finv(uf[x]))%2;
}
void mrg(int a,int b){
int pa=fin(a);int pb=fin(b);
if(pa==pb){
stk.push(0);stkbp.push(isbip);
if(finv(a)==finv(b)){
isbip=0;
}
return;
}
stkbp.push(isbip);
if(sz[pa]<sz[pb]){swap(pa,pb);swap(a,b);}
int va=finv(a);int vb=finv(b);
if(va==vb){
// stkv.push(1);
ufv[pb]=1;
uf[pb]=pa;
sz[pa]+=sz[pb];
}else{
//stkv.push(0);
ufv[pb]=0;
uf[pb]=pa;
sz[pa]+=sz[pb];
}
stk.push(pb);
}
void rollback(){
int pb=stk.top();
if(pb==0){
stk.pop();//stkv.pop();
isbip=stkbp.top();
stkbp.pop();
return;
}
isbip=stkbp.top();
stk.pop();stkbp.pop();
int pa=uf[pb];
sz[pa]-=sz[pb];
uf[pb]=pb;
ufv[pb]=0;
}
int lar[200005];int rar[200005];int lpl[200005];
void precalc(){
for(int i=1;i<=n;i++){
uf[i]=i;
ufv[i]=0;
sz[i]=1;
}
while(stk.size()){stk.pop();}
while(stkbp.size()){stkbp.pop();}
}
void dolid(int lid){
precalc();
isbip=1;
lpl[lid]=0;
for(int i=m+lid-1;i>=lid-1;i--){
mrg(ar[i],br[i]);
if(!isbip){
lpl[lid]=i;break;
}
}
}
signed main(){
cin>>n>>m>>Q;
for(int i=1;i<=m;i++){
cin>>ar[i]>>br[i];
ar[i+m]=ar[i];
br[i+m]=br[i];
}
set<int>st;
for(int i=1;i<=Q;i++){
cin>>lar[i]>>rar[i];
st.insert(lar[i]);
}
for(auto it=st.begin();it!=st.end();it++){
int v=*it;
dolid(v);
}
for(int i=1;i<=Q;i++){
if(rar[i]<lpl[lar[i]]){
cout<<"YES\n";
}else{
cout<<"NO\n";
}
}
}