Submission #1229835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229835		duyngadocton	Bridges (APIO19_bridges)	C++20	100 / 100	2549 ms	135172 KiB

bridges

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ii pair<int,int>
#define iii pair<ii,int>
#define pb push_back
#define eb emplace_back

const int MAX = (int) 1e5;
const int B = 500;

int n, m, q;
int ans[MAX + 5];
stack<ii> st;
int par[MAX + 5], sz[MAX + 5];
int nho[MAX + 5];

int find_root(int u) {
    return (u == par[u]) ? u : find_root(par[u]);
}

void make_set(int u, int v) {
    u = find_root(u), v = find_root(v);
    if(u == v) return;
    if(sz[u] < sz[v]) swap(u, v);
    par[v] = u;
    sz[u] += sz[v];
    st.push(ii(u, v));
}

void rollback(int x) {
    while(st.size() > x) {
        ii x = st.top();
        int u = x.fi, v = x.se;
        par[v] = v;
        sz[u] -= sz[v];
        st.pop();
    }
}

int block(int l) {
    return (l - 1) / B + 1;
}

int start(int l) {
    return (l - 1) * B + 1;
}

int stop(int l) {
    return min(q, l * B);
}

struct edge {
    int u, v, d;
    edge(int _u = 0, int _v = 0, int _d = 0) : u(_u), v(_v), d(_d) {}
} E[MAX + 5];

struct queries {
    int t, x, y;
    queries(int _t = 0, int _x = 0, int _y = 0) : x(_x), y(_y), t(_t) {}
} query[MAX + 5];
int w[MAX + 5];

vector<ii> tmp[MAX + 5];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int u, v, d;
        cin >> u >> v >> d;
        w[i] = d;
        E[i] = edge(u, v, d);
    }
    cin >> q;
    for(int i = 1; i <= q; ++i) {
        int t, x, y;
        cin >> t >> x >> y;
        query[i] = queries(t, x, y);
    }
    for(int SQRT = 1; SQRT <= block(q); ++SQRT) {
        int l = start(SQRT), r = stop(SQRT);
        vector<int> cur;
        while(!st.empty()) st.pop();
        vector<int> qr;
        for(int i = 1; i <= n; ++i) par[i] = i, sz[i] = 1;
        for(int i = 1; i <= m; ++i) nho[i] = 0;
        for(int i = l; i <= r; ++i) if(query[i].t == 1) {
            nho[query[i].x] = 1;
        }
        else {
            qr.pb(i);
        }
        sort(qr.begin(), qr.end(), [](int x, int y) {
            return query[x].y > query[y].y;
        });
        for(int i = 1; i <= m; ++i) if(nho[i] == 0) {
            cur.pb(i);
        }
        for(int i = l; i <= r; ++i) if(query[i].t == 1) {
            w[query[i].x] = query[i].y;
        }
        else {
            for(int j = l; j <= r; ++j) if(query[j].t == 1 && w[query[j].x] >= query[i].y) {
                tmp[i].pb(ii(E[query[j].x].u, E[query[j].x].v));
            }
        }
        sort(cur.begin(), cur.end(), [](int x, int y) {
            return w[x] > w[y];
        });
        int ptr = 0;
        for(int x : qr) {
            while(ptr < cur.size() && w[cur[ptr]] >= query[x].y) {
                int u = E[cur[ptr]].u, v = E[cur[ptr]].v;
                make_set(u, v);
                ++ptr;
            }
            int prev = st.size();
            for(ii j : tmp[x]) {
                int u = j.fi, v = j.se;
                make_set(u, v);
            }
            ans[x] = sz[find_root(query[x].x)];
            rollback(prev);
        }
    }
    for(int i = 1; i <= q; ++i) if(query[i].t == 2) cout << ans[i] << "\n";
}

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