Submission #1046776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046776		ortsac	Joker (BOI20_joker)	C++17	71 / 100	2065 ms	19972 KiB

Joker

#include <bits/stdc++.h>
 
using namespace std;
 
#define pii pair<int, int>
#define fr first
#define se second
 
int block = 4472;
vector<pii> arestas;
int n, m, q;
vector<int> h;
vector<pii> dad;
struct bOp {
    int x, y;
    pii dady;
    int hx;
    bool isbip;
};
vector<bOp> ops;
bool bip = 1;
 
struct Query {
    int l, r, idx;
};
 
bool comp(Query a, Query b) {
    return a.r < b.r;
}
 
const int lst = 47;
vector<Query> qrs[50];
 
pii find(int x) {
    if (dad[x].fr == x) return dad[x];
    pii y = find(dad[x].fr);
    return {y.fr, y.se^dad[x].se};
}
 
void join(int x, int y) {
    auto a = find(x), b = find(y);
    int xdad = a.fr, ydad = b.fr, cx = a.se, cy = b.se;
    if (h[ydad] >= h[xdad]) swap(xdad, ydad);
    bOp newop;
    newop.y = ydad;
    newop.x = xdad;
    newop.dady = dad[ydad];
    newop.hx = h[xdad];
    newop.isbip = bip;
    ops.push_back(newop);
    if (xdad == ydad) {
        if (cx == cy) bip = 0;
        return;
    }
    // x is always bigger now
    dad[ydad] = {xdad, cx == cy};
    if (h[xdad] == h[ydad]) h[xdad]++;
}
 
void rollback() {
    auto u = ops.back();
    ops.pop_back();
    dad[u.y] = u.dady;
    h[u.x] = u.hx;
    bip = u.isbip;
}
 
// bbin?
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    arestas.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> arestas[i].fr >> arestas[i].se;
    }
    vector<bool> ans(q);
    for (int i = 0; i < q; i++) {
        Query x;
        cin >> x.l >> x.r;
        x.l--;
        x.r--;
        x.idx = i;
        qrs[x.l / block].push_back(x);
    }
    for (int t = 0; t < lst; t++) {
        if (qrs[t].empty()) continue;
        dad.clear();
        h.clear();
        ops.clear();
        dad.resize(n + 1);
        h.resize(n + 1);
        bip = 1;
        for (int i = 1; i <= n; i++) {
            dad[i] = {i, 0};
        }
        sort(qrs[t].begin(), qrs[t].end(), comp);
        // initial setup
        int bg = t*block;
        for (int i = 0; i < bg; i++) {
            join(arestas[i].fr, arestas[i].se);
        }
        for (int i = m - 1; i > bg; i--) {
            join(arestas[i].fr, arestas[i].se);
        }
        int cr = bg;
        for (auto u : qrs[t]) {
            int l = u.l, r = u.r;
            for (int i = cr + 1; i <= r; i++) {
                rollback();
            }
            cr = r;
            for (int i = bg; i < l; i++) {
                join(arestas[i].fr, arestas[i].se);
            }
            ans[u.idx] = bip;
            for (int i = 0; i < (l - bg); i++) rollback();
        }
    }
    for (auto u : ans) {
        if (u) cout << "NO\n";
        else cout << "YES\n";
    }
}

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