Submission #374934

#	Time	Username	Problem	Language	Result	Execution time	Memory
374934		valerikk	Collapse (JOI18_collapse)	C++17	100 / 100	8719 ms	29804 KiB

collapse

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7;

int dsu[N], sz[N];
int comps;
vector<int> g[N];
bool vis[N];
int added;

void dfs(int v) {
    vis[v] = 1;
    for (int u : g[v]) {
        if (!vis[u]) {
            ++added;
            dfs(u);
        }
    }
}

int get(int v) {
    return dsu[v] == v ? v : dsu[v] = get(dsu[v]);
}

void unite(int v, int u) {
    v = get(v);
    u = get(u);
    if (v == u) return;
    --comps;
    if (sz[v] > sz[u]) swap(v, u);
    sz[u] += sz[v];
    dsu[v] = u;
}

void init(int n) {
    for (int i = 0; i < n; ++i) {
        dsu[i] = i;
        sz[i] = 1;
    }
    comps = n;
}

vector<int> solve(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p) {
    int c = t.size(), q = w.size();
    for (int i = 0; i < c; ++i) {
        if (x[i] > y[i]) swap(x[i], y[i]);
    }
    vector<int> when(c, c), who(c, -1);
    map<pair<int, int>, int> lst;
    for (int i = 0; i < c; ++i) {
        if (t[i] == 0) {
            lst[{x[i], y[i]}] = i;
        } else {
            who[i] = lst[{x[i], y[i]}];
            when[lst[{x[i], y[i]}]] = i;
        }
    }
    int sq = sqrt(c);
    vector<int> d(q, 0);
    for (int l = 0; l < c; l += sq) {
        int r = min(c, l + sq);
        vector<int> here;
        vector<vector<int>> by_y(n + 1), by_p(n + 1);
        for (int i = 0; i < l; ++i) {
            if (t[i] == 1) continue;
            if (when[i] >= r) {
                by_y[y[i]].push_back(i);
            }
        }
        for (int i = l; i < r; ++i) {
            if (t[i] == 0) here.push_back(i); else here.push_back(who[i]);
        }
        sort(here.begin(), here.end());
        here.erase(unique(here.begin(), here.end()), here.end());
        for (int i = 0; i < q; ++i) {
            if (w[i] >= l && w[i] < r) by_p[p[i]].push_back(i);
        }
        init(n);
        for (int i = 0; i <= n; ++i) {
            for (int id : by_p[i]) {
                d[id] = comps - n + i;
                vector<pair<int, int>> edges;
                for (int edge_id : here) {
                    if (edge_id <= w[id] && w[id] < when[edge_id] && y[edge_id] < i) edges.push_back({get(x[edge_id]), get(y[edge_id])});
                }
                for (auto [u, v] : edges) {
                    g[u] = g[v] = {};
                    vis[u] = vis[v] = 0;
                }
                for (auto [u, v] : edges) {
                    g[u].push_back(v);
                    g[v].push_back(u);
                }
                added = 0;
                for (auto [u, v] : edges) {
                    if (!vis[u]) dfs(u);
                    if (!vis[v]) dfs(v);
                }
                d[id] -= added;
            }
            for (int edge_id : by_y[i]) unite(x[edge_id], y[edge_id]);
        }
    }
    return d;
}

vector<int> simulateCollapse(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p) {
    int c = t.size(), q = w.size();
    for (int i = 0; i < q; ++i) ++p[i];
    auto d1 = solve(n, t, x, y, w, p);
    for (int i = 0; i < c; ++i) {
        x[i] = n - x[i] - 1;
        y[i] = n - y[i] - 1;
    }
    for (int i = 0; i < q; ++i) p[i] = n - p[i];
    auto d2 = solve(n, t, x, y, w, p);
    vector<int> d(q);
    for (int i = 0; i < q; ++i) d[i] = d1[i] + d2[i];
    return d;
}

#ifndef EVAL
int main() {
    freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, c, q;
    cin >> n >> c >> q;
    vector<int> t(c), x(c), y(c);
    for (int i = 0; i < c; ++i) cin >> t[i] >> x[i] >> y[i];
    vector<int> w(q), p(q);
    for (int i = 0; i < q; ++i) cin >> w[i] >> p[i];
    auto d = simulateCollapse(n, t, x, y, w, p);
    for (int i = 0; i < q; ++i) cout << d[i] << '\n';
    return 0;
}
#endif

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