Submission #877218

#	Time	Username	Problem	Language	Result	Execution time	Memory
877218		hotboy2703	Joker (BOI20_joker)	C++14	49 / 100	2004 ms	14812 KiB

Joker

#include<bits/stdc++.h>
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
using ll = int;
ll n,m,q;
namespace DSU{
    ll dsu[200100];
    ll rev[200100];
    void init(){
        memset(dsu,-1,sizeof dsu);
        memset(rev,-1,sizeof rev);
    }
    ll f(ll x){
        if (dsu[x] < 0)return x;
        return (dsu[x] = f(dsu[x]));
    }
    void m(ll x,ll y){
        if (x == -1 || y == -1)return;
        if (dsu[x] > dsu[y])swap(x,y);
        dsu[x] += dsu[y];
        dsu[y] = x;
    }
    bool join(ll x,ll y){
        x = f(x),y = f(y);
        if (x==y)return 0;
        if (rev[x] == y)return 1;
        else{
            m(x,rev[y]);
            m(rev[x],y);
            x = f(x);
            y = f(y);
            rev[x] = y;
            rev[y] = x;
            return 1;
        }
    }
}
pll a[200100];
ll color[200100];
ll pre[200100];
vector <ll> g[200100];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m>>q;
    for (ll i = 1;i <= m;i ++)cin>>a[i].fi>>a[i].se;

    if (q <= 2000){
        while (q--){
            ll l,r;
            cin>>l>>r;
            for (ll i = 1;i <= n;i ++){
                color[i] = -1;
                g[i].clear();
            }
            for (ll i = 1;i < l;i ++){
                g[a[i].fi].push_back(a[i].se);
                g[a[i].se].push_back(a[i].fi);
            }
            for (ll i = r + 1;i <= m;i ++){
                g[a[i].fi].push_back(a[i].se);
                g[a[i].se].push_back(a[i].fi);
            }
            bool ok = 0;
            for (ll i = 1;i <= n;i ++){
                if (color[i] == -1){
                    color[i] = 0;
                    queue <ll> q;
                    q.push(i);
                    while (!q.empty()){
                        ll u = q.front();
                        q.pop();
                        for (auto v:g[u]){
                            if (color[v] == -1){
                                color[v] = 1-color[u];
                                q.push(v);
                            }
                            else{
                                if (color[v] == color[u]){
                                    ok = 1;
                                    break;
                                }
                            }
                        }
                    }
                    if (ok)break;
                }
            }
            cout<<(ok?"YES":"NO")<<'\n';
        }
    }
    else{
        for (ll i = 0;i < m;i ++){
            pre[i] = m+1;
        }
        for (ll i = 0;i < min(m,201);i ++){
            DSU::init();
            bool ok = 1;
            for (ll j = 1;j <= i;j ++){
                ok &= DSU::join(a[j].fi,a[j].se);
            }
            if (ok == 0)break;
            while (pre[i] > i + 1 && DSU::join(a[pre[i]-1].fi,a[pre[i] - 1].se)){
                pre[i]--;
            }
        }
        for (ll i = 1;i <= q;i ++){
            ll l,r;
            cin>>l>>r;
            if (r < pre[l-1] - 1){
                cout<<"YES";
            }
            else{
                cout<<"NO";
            }
            cout<<'\n';
        }
    }
    return 0;
}

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