Submission #1227290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227290		Almonther	Joker (BOI20_joker)	C++20	0 / 100	2093 ms	27816 KiB

Joker

#include<bits/stdc++.h>

#define ll long long
#define co cout<<

using namespace std;
// stuff
const int maxn=2e5+5;
ll n,m,q;
vector<pair<ll,ll>>edges;
vector<pair<ll,ll>>qu[maxn];
vector<ll>v[maxn],v1[maxn];
ll ans[maxn];
ll c[maxn],bad=0,bad1=0,c1[maxn];
void dfs(ll x){
    ll red=0,blue=0;
    for(auto i:v[x]){
        if(c[i]==1) red=1;
        if(c[i]==2) blue=1;
    }
    if((red==1&&blue==1)||(red==1&&c[x]==1)||(blue==1&&c[x]==2)){
        bad=1;
        return;
    }
    if(blue) c[x]=1;
    else c[x]=2;
    for(auto i:v[x]) if(c[i]==0) dfs(i);
    v[x].clear();
    red=0,blue=0;
    for(auto i:v1[x]){
        if(c1[i]==1) red=1;
        else if(c1[i]==2) blue=1;
    }
    if((red==1&&blue==1)||(red==1&&c1[x]==1)||(blue==1&&c1[x]==2)){
        bad1=1;
        return;
    }
    if(blue) c1[x]=1;
    else c1[x]=2;
    for(auto i:v1[x]) if(c1[i]==0) dfs(i);
    v1[x].clear();
}
void solve(){
    cin>>n>>m>>q;
    for(int i=0;i<m;i++){
        ll a,b;
        cin>>a>>b;
        edges.push_back({a,b});
    }
    for(int i=0;i<q;i++){
        ll l,r;
        cin>>l>>r;
        qu[r].push_back({l-1,i});
    }
    for(int i=0;i<=m;i++) sort(qu[i].begin(),qu[i].end());
    for(int i=m;i>=0;i--){
        if(i<m){
            v[edges[i].first].push_back(edges[i].second);
            v[edges[i].second].push_back(edges[i].first);
            dfs(edges[i].first);
            v[edges[i].first].clear();
            v[edges[i].second].clear();
        }
        if(qu[i].size()==0) continue;
        ll pt=0;
        for(int i=1;i<=n;i++) c1[i]=c[i],bad1=bad;
        for(int j=0;j<=i;j++){
            if(j){
                v1[edges[j].first].push_back(edges[j].second);
                v1[edges[j].second].push_back(edges[j].first);
                dfs(edges[j].first);
                v1[edges[j].first].clear();
                v1[edges[j].second].clear();
            }
            while(pt<qu[i].size()&&qu[i][pt].first==j){
                ans[qu[i][pt].second]=bad|bad1,pt++;
            }
            if(qu[i].size()==pt) break;
        }
    }
    for(int i=0;i<q;i++) co ((ans[i])?"YES\n":"NO\n");
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _=1;
    // cin>>_;
    while(_--) solve();
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 25
• Subtask 3: 0 / 10
• Subtask 4: 0 / 22
• Subtask 5: 0 / 29
• Subtask 6: 0 / 6