답안 #837996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
837996	2023-08-26T03:48:48 Z	1075508020060209tc	Joker (BOI20_joker)	C++14	25 / 100	67 ms	8472 KB

Joker

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #837996

Compilation message

Subtask #1 0 / 6.0

Subtask #2 0 / 8.0

Subtask #3 25.0 / 25.0

Subtask #4 0 / 10.0

Subtask #5 0 / 22.0

Subtask #6 0 / 29.0

Subtask #1
0 / 6.0

Subtask #2
0 / 8.0

Subtask #3
25.0 / 25.0

Subtask #4
0 / 10.0

Subtask #5
0 / 22.0

Subtask #6
0 / 29.0