Submission #257795

#	Time	Username	Problem	Language	Result	Execution time	Memory
257795		4fecta	Bridges (APIO19_bridges)	C++14	44 / 100	3063 ms	9216 KiB

bridges

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#define ll long long
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define readl(_s) getline(cin, (_s));
#define boost() cin.tie(0); cin.sync_with_stdio(0)

struct edge {
    int u = 0, v = 0, w = 0, i = 0, t = 0;
};

struct query {
    int t = 0, u = 0, v = 0, i = 0;
};

bool cmp(edge x, edge y) {
    return x.w > y.w;
}

bool cmq(query x, query y) {
    return x.u > y.u;
}

const int MN = 50005, MM = 100005, SQRT = 1000;

int n, m, q, par[MN], sz[MN], unst[MM], ans[MM], tmp, vis[MN];
edge e[MM], E[MM];
query Q[MM];
vector<int> a[MN];

int find(int x) {
    return x == par[x] ? x : par[x] = find(par[x]);
}

inline bool merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (sz[x] > sz[y]) {
        par[y] = par[x];
        sz[x] += sz[y];
    } else {
        par[x] = par[y];
        sz[y] += sz[x];
    }
    return true;
}

void dfs(int cur) {
    vis[cur] = 1;
    tmp += sz[cur];
    for (int nxt : a[cur]) if (!vis[nxt]) dfs(nxt);
}

void sfd(int cur) {
    vis[cur] = 0;
    for (int nxt : a[cur]) if (vis[nxt]) sfd(nxt);
}

int main() {
    boost();

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> e[i].u >> e[i].v >> e[i].w; e[i].i = i;
        E[i] = e[i];
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> Q[i].t >> Q[i].u >> Q[i].v; Q[i].i = i;
        if (Q[i].t == 2) swap(Q[i].u, Q[i].v);
    }
    for (int I = 1; I <= q; I += SQRT) {
        int lft = I, rit = min(q, I + SQRT - 1); //range of currently processed block
        for (int i = 1; i <= m; i++) e[i] = E[i], unst[i] = 0;
        sort(e + 1, e + m + 1, cmp);
        vector<query> qs;
        deque<edge> edges;
        vector<int> chg;
        for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
        for (int i = lft; i <= rit; i++) {
            if (Q[i].t == 1) {
                unst[Q[i].u] = 1;
                chg.push_back(Q[i].u);
                edges.push_front({E[Q[i].u].u, E[Q[i].u].v, Q[i].v, i, Q[i].u});
            } else {
                qs.push_back(Q[i]);
            }
        }
        sort(chg.begin(), chg.end());
        chg.erase(unique(chg.begin(), chg.end()), chg.end());
        sort(qs.begin(), qs.end(), cmq);
        int id = 1;
        for (query cur : qs) { //maybe we try to run dfs instead of dsu + undo will get rid of log?
            while (id <= m && e[id].w >= cur.u) {
                if (!unst[e[id].i]) merge(e[id].u, e[id].v);
                id++;
            }
            vector<pii> add;
            for (edge ed : edges) {
                if (ed.i > cur.i || !unst[ed.t]) continue;
                unst[ed.t] = 0;
                if (ed.w >= cur.u) { //add this as an edge to the graph
                    int u = find(ed.u), v = find(ed.v);
                    a[u].push_back(v);
                    a[v].push_back(u);
                    add.push_back({u, v});
                }
            }
            for (int i : chg) {
                if (unst[i] && E[i].w >= cur.u) { //add this as an edge to the graph
                    int u = find(E[i].u), v = find(E[i].v);
                    a[u].push_back(v);
                    a[v].push_back(u);
                    add.push_back({u, v});
                }
            }
            tmp = 0; dfs(find(cur.v));
            ans[cur.i] = tmp;
            //reset all ur stuff
            sfd(find(cur.v));
            for (pii p : add) a[p.f].pop_back(), a[p.s].pop_back();
            for (int i : chg) unst[i] = 1;
        }
        for (int i = lft; i <= rit; i++) {
            if (Q[i].t == 1) E[Q[i].u].w = Q[i].v;
            else printf("%d\n", ans[i]);
        }
    }

    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27