Submission #649810

#	Time	Username	Problem	Language	Result	Execution time	Memory
649810		DJeniUp	Joker (BOI20_joker)	C++17	49 / 100	2092 ms	10504 KiB

Joker

#include "bits/stdc++.h"
//#pragma GCC optimize("O3")

using namespace std;

typedef int ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef long double ld;

#define fr first
#define sc second
#define pb push_back
#define INF 100000000007
#define endl '\n'
#define MOD 998244353
#define N 200007

ll n,m,q,p[N],res[N],h[N],f,k;

struct Q{
    ll l,r;
}o[N];

struct D{
    ll l,r;
}d[N];

set<ll>s;

ll P(ll x){
    if(p[x]!=x){
        ll g=P(p[x]);
        h[x]+=h[p[x]];
        h[x]%=2;
        p[x]=g;
    }
    return p[x];
}

ll H(ll x){
    ll r1=0;
    while(p[x]!=x){
        r1+=h[x];
        x=p[x];
    }
    return r1;
}

void A(ll x,ll y){
    if(rand()%2)swap(x,y);
    ll x1=P(x);
    ll y1=P(y);
    h[x1]=H(x)+1+H(y);
    h[x1]%=2;
    p[x1]=y1;
    return ;
}

int main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //cin>>n>>m>>q;
    scanf("%d %d %d", &n, &m, &q);
    //s.insert(0);
    for(int i=1;i<=m;i++){
        //cin>>d[i].l>>d[i].r;
        scanf("%d %d", &d[i].l, &d[i].r);
    }
    for(int i=1;i<=q;i++){
        //cin>>o[i].l>>o[i].r;
        scanf("%d %d", &o[i].l, &o[i].r);
        s.insert(o[i].l-1);
    }
    for(auto it:s){
        res[it]=0;
        for(int i=1;i<=n;i++){
            p[i]=i;
            h[i]=0;
        }
        for(int i=1;i<=it;i++){
            if(P(d[i].l)!=P(d[i].r)){
                A(d[i].l,d[i].r);
            }else if(H(d[i].l)%2==H(d[i].r)%2){
                res[it]=m+1;
            }
        }
        if(res[it]!=0)continue;
        for(int i=m;i>=it;i--){
            if(P(d[i].l)==P(d[i].r) && H(d[i].l)%2==H(d[i].r)%2){
                res[it]=i;
                break;
            }else if(P(d[i].l)!=P(d[i].r))A(d[i].l,d[i].r);
        }
    }
    
    for(int i=1;i<=q;i++){
        
        if(res[o[i].l-1]>o[i].r)printf("YES\n");
        else printf("NO\n");
    }
    
    
    return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf("%d %d", &d[i].l, &d[i].r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         scanf("%d %d", &o[i].l, &o[i].r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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