Submission #1131470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131470		vladilius	Collapse (JOI18_collapse)	C++20	30 / 100	153 ms	40664 KiB

collapse

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int N = 4e5;

struct dsu{
    vector<int> sz, p;
    vector<pair<int&, int>> hist;
    vector<int> sizes;
    int n, cc;
    void init(int ns){
        n = ns;
        sz.resize(n + 1);
        p.resize(n + 1);
        for (int i = 1; i <= n; i++){
            sz[i] = 1;
            p[i] = i;
        }
        cc = n;
    }
    int get(int v){
        return (v == p[v]) ? v : get(p[v]);
    }
    void unite(int x, int y){
        x = get(x); y = get(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        hist.pb({p[x], p[x]});
        p[x] = y;
        hist.pb({sz[y], sz[y]});
        sz[y] += sz[x];
        hist.pb({cc, cc});
        cc--;
    }
    void check_point(){
        sizes.pb((int) hist.size());
    }
    void roll_back(){
        while (hist.size() != sizes.back()){
            hist.back().ff = hist.back().ss;
            hist.pop_back();
        }
        sizes.pop_back();
    }
};

vector<pii> ed[N];
vector<int> out, qs[N];
int k;
dsu T;

void add(int v, int tl, int tr, int l, int r, pii x){
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r){
        ed[v].pb(x);
        return;
    }
    int tm = (tl + tr) / 2, vv = 2 * v;
    add(vv, tl, tm, l, r, x);
    add(vv + 1, tm + 1, tr, l, r, x);
}

void solve(int v, int tl, int tr){
    T.check_point();
    for (auto [x, y]: ed[v]){
        T.unite(x, y);
    }
    if (tl == tr){
        for (int ii: qs[tl]){
            out[ii] = T.cc;
        }
    }
    else {
        int tm = (tl + tr) / 2, vv = 2 * v;
        solve(vv, tl, tm);
        solve(vv + 1, tm + 1, tr);
    }
    T.roll_back();
}

vector<int> simulateCollapse(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p){
    int m = (int) t.size();
    x.insert(x.begin(), 0);
    y.insert(y.begin(), 0);
    t.insert(t.begin(), 0);
    for (int i = 1; i <= m; i++){
        x[i]++; y[i]++;
    }
    int q = (int) w.size();
    for (int i = 0; i < q; i++){
        p[i]++; w[i]++;
    }
    int P = p[0];
    
    map<pii, int> mp;
    for (int i = 1; i <= m; i++){
        if (x[i] > y[i]) swap(x[i], y[i]);
        if (y[i] <= P || x[i] > P){
            if (!t[i]){
                if (mp.find({x[i], y[i]}) == mp.end()){
                    mp[{x[i], y[i]}] = i;
                }
            }
            else {
                add(1, 1, m, mp[{x[i], y[i]}], i - 1, {x[i], y[i]});
                mp.erase({x[i], y[i]});
            }
        }
    }
    for (auto tt: mp){
        add(1, 1, m, tt.ss, m, tt.ff);
    }
    for (int i = 0; i < q; i++) qs[w[i]].pb(i);
    T.init(n);
    out.resize(q);
    solve(1, 1, m);
    return out;
}

• Subtask 1: 0 / 5
• Subtask 2: 30 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35