Submission #1112102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112102		Ciprian	Joker (BOI20_joker)	C++14	0 / 100	2057 ms	11464 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pi pair<int,int>
const int N=2e5+4;
vector<int> root(N), dist(N);
int find(int x){
    if(x==root[x])return x;
    
    return find(root[x]);
}
int cnt(int x){
    if(x==root[x])return dist[x];
    return dist[x] + cnt(root[x]);
    
}
bool unify(int x, int y){
    int a=find(x);
    int b=find(y);
    int c1=cnt(x), c2=cnt(y);
   // cout<<a<<" "<<b<<endl;
    if(a!=b){
        root[b]=a;
        dist[b]=1;
    }
    if(a==b && c1%2==c2%2){
        return true;
    }
    
    return false;
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    vector<pi> edge;
    for(int j=0; j<m; j++){
        int u,v;
        cin>>u>>v;
        edge.push_back({u,v});
    }for(int j=0; j<q; j++){
        int l,r;
        cin>>l>>r;
        l--;
        r--;
        for(int i=1; i<=n; i++)root[i]=i, dist[i]=0;
        string ans="NO";
        for(int i=0; i<l; i++){
            auto p=edge[i];
            if(unify(p.first, p.second)){
                ans="YES";
                //cout<<cnt(p.first)<<" "<<cnt(p.second)<<endl;
            }
        }for(int i=r+1; i<m; i++){
            auto p=edge[i];
            if(unify(p.first, p.second)){
                ans="YES";
                //cout<<cnt(p.first)<<" "<<cnt(p.second)<<endl;
            }
        }cout<<ans<<endl;
    }

    return 0;
}

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