Submission #922121

#	Time	Username	Problem	Language	Result	Execution time	Memory
922121		406	Bridges (APIO19_bridges)	C++17	100 / 100	1785 ms	106616 KiB

bridges

    #include "bits/stdc++.h"
    #define FOR(i, a, b) for (int i = (a); i < (b); i++) 
    using namespace std;
    const long long INF = 1ll << 60;
    const int N = 1e5 + 5;
     
    int dpr[N];
    vector<array<int, 3>> undo;
    int gpr(int x) { 
    	while (dpr[x] >= 0) x = dpr[x];
    	return x;
    }
    bool merge(int u, int v) {
    	u = gpr(u), v = gpr(v);
    	if (u == v) return false;
    	if (dpr[u] < dpr[v]) swap(u, v); //v is bigger now
    	undo.push_back({u, v, dpr[u]});
    	dpr[v] += dpr[u];
    	dpr[u] = v;
    	return true;
    }
    void rollback() {
    	const auto &a = undo.back();
    	dpr[a[0]] = a[2];
    	dpr[a[1]] -= a[2];
    	undo.pop_back();
    }
     
    const int SQ = 1000;
    const int SQ2 = N / SQ + 5;
    int a[N], b[N], U[N], W[N], V[N], n, m, q, ans[N];
    short t[N];
     
    void solve() {
    	//t = 1 CHANGE
    	//t = 2 SOAL
    	FOR(i, 0, SQ2) {
    		int L = i * SQ, R = min(q, (i + 1) * SQ);
    		if (L >= q) break;
     
    		memset(dpr, -1, sizeof dpr);
     
    		bitset<N> change = 0, mark = 0;
    		vector<int> Q, E, NE;
     
    		FOR(j, L, R) {
    			if (t[j] == 1) change[a[j]] = true;
    			else Q.push_back(j);
    		}
    		FOR(j, 0, m) (change[j] ? NE : E).push_back(j);
     
    		sort(E.rbegin(), E.rend(), [&](const int x, const int y) {return W[x] < W[y];});
    		sort(Q.begin(), Q.end(), [&](const int x, const int y) {return b[x] < b[y];});
     
    		for (auto qid: Q) {
    			while (E.size() && W[E.back()] <= b[qid]) {
    				merge(U[E.back()], V[E.back()]);
    				E.pop_back();
    			}
    			int cnt = 0;
    			for (int j = qid; j >= L; j--) if (t[j] == 1 && !mark[a[j]]) {
    				if (b[j] <= b[qid]) {
    					cnt += merge(U[a[j]], V[a[j]]);
    					mark[a[j]] = true;
    				}
    				mark[a[j]] = true;
    			}
    			for (auto e: NE) if (!mark[e]) {
    				mark[e] = true;
    				if (W[e] <= b[qid]) {
    					cnt += merge(U[e], V[e]);
    					mark[e] = true;
    				}
    			}
    			ans[qid] = dpr[gpr(a[qid])];
     
    			while (cnt--) rollback();
     
    			FOR(j, L, qid) mark[a[j]] = false;
    			for (auto e: NE) mark[e] = false;
    		}
    		FOR(j, L, R) if (t[j] == 1) W[a[j]] = b[j];
    	}
    	FOR(i, 0, q) if (t[i] == 2) cout << -ans[i] << '\n';
    }
     
    signed main() {
    	ios::sync_with_stdio(0), cin.tie(0);
    	cin >> n >> m;
    	FOR(i, 0, m) {
    		cin >> U[i] >> V[i] >> W[i];
    		U[i]--, V[i]--;
    		W[i] = -W[i];
    	}
    	cin >> q;
    	FOR(i, 0, q) {
    		cin >> t[i] >> a[i] >> b[i];
    		a[i]--;
    		b[i] = -b[i];
    	}
    	solve();
     
    	return 0;
    }

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