Submission #1144162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144162		TB_	Joker (BOI20_joker)	C++17	14 / 100	2095 ms	33736 KiB

Joker

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

// #undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")

#define ll long long
#define INF ((ll)(1e9+7))
#define fo(i, n) for(ll i=0;i<((ll)n);i++)
#define deb(x) cout << #x << " = " << (x) << endl;
#define deb2(x, y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LSOne(S) ((S) & (-S))
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpii> vvpii;
typedef vector<vpl> vvpl;

struct UnionFind{
    int n, c;
    vl p, color, height;
    vpl histp, histc, histh;
    vl res = {0};

    UnionFind(int n) : n(n){
        p.assign(n, -1);
        color.assign(n, 0);
        height.assign(n, 1);
        fo(i, n)p[i] = i;
    }


    int find(int x){
        c+=color[x];
        if(p[x] == x)return x;
        return find(p[x]);
    }

    void unite(int prea, int preb){
        c = 0;
        int a = find(prea);
        int b = find(preb);
        if(a == b){
            histp.pb({-1, -1});
            histc.pb({-1, -1});
            res.pb(res.back()|(c%2 == 0));
            return;
        }
        if(height[a] > height[b])swap(a, b);
        res.pb(res.back());
        histp.pb({b, p[b]});
        histc.pb({b, color[b]});
        histh.pb({a, height[a]});
        p[b] = a;
        if(height[a] == height[b])height[a]++;

        if(c%2 == 0){ 
            color[b] ^= 1;
        }
    }

    void rollback(){
        // rev
        // deb(histp.size());
        if(histp.back().F != -1)p[histp.back().F] = histp.back().S;
        if(histc.back().F != -1)color[histc.back().F] = histc.back().S;

        res.pop_back();
        histp.pop_back();
        histc.pop_back();
    }
};

int main() {
    // cout << fixed << setprecision(20);
    cin.tie(0)->sync_with_stdio(0);

    ll n, m, q;
    cin >> n >> m >> q;
    vpl v(m);

    fo(i, m){
        cin >> v[i].F >> v[i].S;
        v[i].F--;
        v[i].S--;
    }

    ll block_size = 4500;
    vector<vector<tuple<ll, ll, ll>>> queries(2000);
    fo(i, q){
        ll l, r;
        cin >> l >> r;
        l--; r--;
        queries[l/block_size].pb({r, l, i});
    }
    vl ans(q);
    fo(block, queries.size()){
        if(block*block_size >= m)break;
        if(queries[block].empty())continue;
        sort(all(queries[block]));
        UnionFind uf(n+2);

        fo(i, block*block_size)uf.unite(v[i].F, v[i].S);
        for(ll i = m-1;i>=block*block_size;i--){
            uf.unite(v[i].F, v[i].S);
        }
        ll hi = block*block_size;
        for(auto &[r, l, ind] : queries[block]){
            while(hi<=r){
                uf.rollback();
                hi++;
            }

            fo(i, l-block*block_size){
                uf.unite(v[i+block*block_size].F, v[i+block*block_size].S);
            }
            ans[ind] = uf.res.back();
            for(ll i = l-block*block_size-1;i>=0;i--){
                uf.rollback();
            }

        }
    }

    fo(i, q)cout << (ans[i] ? "YES" : "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