Submission #1227332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227332		Almonther	Joker (BOI20_joker)	C++20	14 / 100	2096 ms	18096 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<ll>v[maxn];
ll ans[maxn];
ll c[maxn],bad=0;
void dfs(ll x,ll last){
    if(c[x]) return;
    if(c[last]==1) c[x]=2;
    else c[x]=1;
    for(auto i:v[x]){
        if(c[x]==c[i]) bad=1;
        dfs(i,x);
    }
}
void solve(){
    cin>>n>>m>>q;
    for(int i=0;i<m;i++){
        ll a,b;
        cin>>a>>b;
        edges.push_back({a,b});
    }
    while(q--){
        ll l,r;
        cin>>l>>r;
        for(int i=0;i<l-1;i++){
            v[edges[i].first].push_back(edges[i].second);
            v[edges[i].second].push_back(edges[i].first);
        }
        for(int i=r;i<m;i++){
            v[edges[i].first].push_back(edges[i].second);
            v[edges[i].second].push_back(edges[i].first);
        }
        for(int i=1;i<=n;i++) dfs(i,0);
        for(int i=1;i<=n;i++){
            v[i].clear();
            c[i]=0;
        }
        co ((bad)?"YES\n":"NO\n");
        bad=0; 
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _=1;
    // cin>>_;
    while(_--) solve();
}

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