Submission #602327

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
602327	2022-07-22T22:13:15 Z	OttoTheDino	Joker (BOI20_joker)	C++17	25 / 100	166 ms	20476 KB

Joker

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

#define rep(i,s,e)                          for (int i = s; i <= e; ++i)
#define rrep(i,s,e)                         for (int i = s; i >= e; --i)
#define fi                                  first
#define se                                  second
#define pb                                  push_back
#define len(a)                              (int)a.size()
typedef vector<int> vi;
typedef pair<int,int> ii;

const int mx = 2e5;
vi adj[mx+1];

int par[mx+1], h[mx+1], tp[mx+1], dp[mx+1], cnt, m, on = 0;
ii e[mx+1];
vector<vi> history;

ii get_par (int u) {
    if (u==par[u]) return {u, tp[u]};
    ii res = get_par (par[u]); 
    ii ans = {res.fi, res.se^tp[u]};
    return {ans};
}

bool merge (int u, int v) {
    ii paru = get_par(u), parv = get_par(v);
    if (paru.fi==parv.fi) {
        history.pb({parv.fi, parv.fi, paru.se==parv.se, 0});
        return paru.se==parv.se;
    }
    if (h[paru.fi]<h[parv.fi]) swap(paru, parv);
    history.pb({parv.fi, paru.fi, h[paru.fi]==h[parv.fi], parv.se==paru.se});
    h[paru.fi] += h[paru.fi]==h[parv.fi];
    par[parv.fi] = paru.fi; 
    tp[parv.fi] ^= parv.se==paru.se;
    return 0;
}

int rollback (int t) {
    int sum = 0;
    while (t--) {
        int a = history.back()[0], b = history.back()[1], c = history.back()[2], d = history.back()[3];
        history.pop_back();
        if (a==b) {
            sum += c;
            continue;
        }
        par[a] = a;
        h[b] -= c;
        tp[a] ^= d;
    }
    return sum;
}

void go (int l1, int l2, int r1, int r2) {

    if (l1==0 && l2==1) {
        on = 1;
    }
    else {
        on = 0;
    }
    if (l1>=3) return;

    if (r1==r2) {
        rep (i,l1,l2) dp[i] = r1;
        return;
    }

    int lm = (l1+l2)/2, rm = r2, steps = 0;
    rep (i,l1,lm) {
        if (i) {
            cnt += merge(e[i].fi, e[i].se);
            steps++;
        }
    }

    bool suc = 0;

    if (cnt) {
        suc = 1;
        goto nxt;
    }

    while (true) {
        if (rm<=m) {
            cnt += merge(e[rm].fi, e[rm].se);
            steps++;
        }
        if (cnt) {
            suc = 1;
            break;
        }
        if (rm==lm+1) break;
        --rm;
    }

    nxt:

    cnt -= rollback(steps);


    if (!suc) {
        //don't need to do anything with dp[l1]...dp[lm]
        if (l2>=lm+1) {
            steps = 0;
            rep (i,l1,lm) {
                if (i) {
                    cnt += merge(e[i].fi, e[i].se);
                    steps++;
                }
            }
            go(lm+1, l2, lm+2, r2); 
            cnt -= rollback(lm-l1);
        }
        return;
    }

    dp[lm] = rm;

    if (lm-1>=l1) {
        steps = 0;
        rep (i,rm+1,r2) {
            if (i<=m) {
                cnt += merge(e[i].fi, e[i].se); 
                steps++;
            }
        }
        go (l1, lm-1, r1, rm);
        cnt -= rollback(steps);
    }

    if (l2>=lm+1) {
        steps = 0;
        rep (i,l1,lm) {
            if (i) {
                cnt += merge(e[i].fi, e[i].se);
                steps++;
            }
        }
        go (lm+1,l2,max(lm+2,r1),r2);
        cnt -= rollback(steps);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, q; cin >>n >> m >> q;

    rep (i,1,n) {
        par[i] = i;
        h[i] = 1;
    }

    rep (i,1,m) cin >> e[i].fi >> e[i].se;


    go (0,m,1,m+1);

    while (q--) {
        int l, r; cin >> l >> r;
        cout << (r<dp[l-1]?"YES":"NO") << "\n";
    }

    return 0;
}

Subtask #1
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4996 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Incorrect	2 ms	4948 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4996 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Incorrect	2 ms	4948 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4996 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	109 ms	13800 KB	Output is correct
4	Correct	91 ms	20476 KB	Output is correct
5	Correct	96 ms	14836 KB	Output is correct
6	Correct	124 ms	18036 KB	Output is correct
7	Correct	105 ms	17912 KB	Output is correct
8	Correct	146 ms	16872 KB	Output is correct
9	Correct	114 ms	17372 KB	Output is correct
10	Correct	116 ms	18788 KB	Output is correct
11	Correct	106 ms	17764 KB	Output is correct
12	Correct	139 ms	19244 KB	Output is correct
13	Correct	115 ms	16824 KB	Output is correct
14	Correct	116 ms	17360 KB	Output is correct
15	Correct	111 ms	18368 KB	Output is correct
16	Correct	166 ms	19260 KB	Output is correct