oj.uz

Submission #837996

# Submission time Handle Problem Language Result Execution time Memory
837996 2023-08-26T03:48:48 Z 1075508020060209tc Joker (BOI20_joker) C++14
25 / 100
 67 ms 8472 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
 
#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 finv(int x){
if(uf[x]==x){return 0;}
return (ufv[x]+finv(uf[x]))&1;
}
int fin(int x){
if(uf[x]==x){return x;}
int v=(ufv[x]+finv(uf[x]))&1;
ufv[x]=v;
uf[x]=fin(uf[x]);
return uf[x];
}
 
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();}
 
}
 int all;
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;
    }
}
if(lid==0&&lpl[lid]==0){
    all=1;
}
}
 
signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
    
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]);
}
dolid(0);
if(!all){
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";
    }
}
 
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 368 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Incorrect 0 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 368 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Incorrect 0 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 57 ms 6992 KB Output is correct
4 Correct 55 ms 8140 KB Output is correct
5 Correct 53 ms 7976 KB Output is correct
6 Correct 52 ms 7012 KB Output is correct
7 Correct 54 ms 6960 KB Output is correct
8 Correct 50 ms 6744 KB Output is correct
9 Correct 52 ms 7116 KB Output is correct
10 Correct 63 ms 8472 KB Output is correct
11 Correct 53 ms 6988 KB Output is correct
12 Correct 57 ms 7900 KB Output is correct
13 Correct 67 ms 6084 KB Output is correct
14 Correct 53 ms 6540 KB Output is correct
15 Correct 66 ms 7480 KB Output is correct
16 Correct 58 ms 8180 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 368 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Incorrect 0 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 368 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Incorrect 0 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 368 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Incorrect 0 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -