Submission #1148321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148321		byunjaewoo	Joker (BOI20_joker)	C++20	14 / 100	2093 ms	36892 KiB

Joker

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=200010;
int n, m, q, u[N], v[N], p[N];
int flag, g[N], c[N];
vector<vector<array<int, 3>>> vec;
vector<int> com[N], vec2;

int Find(int x) { return (g[x]>=0)?Find(g[x]):x; }
void Union(int u, int v) {
    int uu=Find(u), vv=Find(v);
    if(uu==vv) {
        vec.push_back({}), vec2.push_back(flag);
        if(c[u]==c[v]) flag=true;
        return;
    }
    vector<array<int, 3>> tmp;
    if(-g[uu]>-g[vv]) swap(uu, vv);
    if(c[u]==c[v]) {
        for(int i:com[uu]) tmp.push_back({0, i, c[i]}), c[i]=1-c[i];
    }
    reverse(com[uu].begin(), com[uu].end());
    for(int i:com[uu]) tmp.push_back({2, uu, vv}), com[vv].push_back(i);
    com[uu].clear();
    tmp.push_back({1, uu, g[uu]}), tmp.push_back({1, vv, g[vv]});
    g[vv]+=g[uu], g[uu]=vv;
    vec.push_back(tmp), vec2.push_back(flag);
}
void RollBack(int cnt) {
    while(cnt--) {
        flag=vec2.back();
        for(auto [op, x, y]:vec.back()) {
            if(op==0) c[x]=y;
            else if(op==1) g[x]=y;
            else {
                com[x].push_back({com[y].back()}), com[y].pop_back();
            }
        }
        vec.pop_back(), vec2.pop_back();
    }
}

void F(int l, int r, int s, int e) {
    if(l>r) return;
    int mid=(l+r)/2, cnt=0;
    for(int i=l; i<mid; i++) Union(u[i], v[i]), cnt++;
    for(int i=e; i>=max(s, mid); i--) {
        if(flag) {
            p[mid]=i; break;
        }
        Union(u[i], v[i]), cnt++;
    }
    if(!p[mid]) {
        RollBack(cnt), cnt=0;
        //for(int i=e; i>=mid; i--) Union(u[i], v[i]), cnt++;
        //F(l, mid-1, s, min(e, mid-1));
        F(l, mid-1, s, e);
        //RollBack(cnt), cnt=0;
        for(int i=l; i<=mid; i++) Union(u[i], v[i]), cnt++;
        //F(mid+1, r, max(s, mid+1), e);
        F(mid+1, r, s, e);
        RollBack(cnt);
    }
    else {
        RollBack(cnt), cnt=0;
        for(int i=e; i>=p[mid]+1; i--) Union(u[i], v[i]), cnt++;
        F(l, mid-1, s, p[mid]);
        RollBack(cnt), cnt=0;
        for(int i=l; i<=mid; i++) Union(u[i], v[i]), cnt++;
        F(mid+1, r, p[mid], e);
        RollBack(cnt);
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1; i<=m; i++) cin>>u[i]>>v[i];
    fill(g+1, g+n+1, -1);
    for(int i=1; i<=n; i++) com[i].push_back(i);
    F(1, m, 1, m);
    while(q--) {
        int l, r; cin>>l>>r;
        if(r<=p[l]) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

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