Submission #1227257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227257		m5588ohammed	Joker (BOI20_joker)	C++20	39 / 100	2095 ms	25664 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define mod 1000000009
#define int long long
#define double long double
int n,m,q;
vector <array<int,2>> v[200001];
int disc[200001],odd=0,ans[200001];
set <int> qu;
vector <array<int,2>> query;
void solve(int i,int cnt,int l1,int r1){
    disc[i]=cnt;
    for(auto [j,idx]:v[i]){
        if(l1<=idx&&idx<=r1) continue;
        if(disc[j]!=0&&(disc[i]-disc[j])%2==0) odd++;
        if(disc[j]==0) solve(j,cnt+1,l1,r1);
    }
    return;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        v[a].push_back({b,i});
        v[b].push_back({a,i});
    }
    for(int i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        qu.insert(l);
        query.push_back({l,r});
    }
    for(int bg:qu){
        int l=bg,r=m;
        ans[bg]=1e9;
        while(l<=r){
            int mid=(l+r)/2;
            memset(disc,0,sizeof disc);
            odd=0;
            for(int i=1;i<=n;i++){
                if(disc[i]==0) solve(i,1,bg,mid);
            }
            if(odd==0){
                ans[bg]=mid;
                r=mid-1;    
            }
            else l=mid+1;
        }
    }
    for(auto [l,r]:query){
        if(ans[l]<=r) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

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