Submission #1281443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281443		Jawad_Akbar_JJ	Bridges (APIO19_bridges)	C++20	59 / 100	3097 ms	71356 KiB

bridges

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;
const int N = 100005, K = 320;
stack<int> Par[N];
int seen[N], Sz[N], Ans[N], a[N], b[N], c[N], x[N], y[N], z[N], lst[N];

int root(int v){
	while (Par[v].size() > 0)
		v = Par[v].top();
	return v;
}

void solve(int n, int m, int q){
	vector<pair<int,int>> vec, Quer;
	for (int i=1;i<=q;i++){
		if (x[i] == 1)
			seen[y[i]] = (seen[y[i]] == 0 ? i : seen[y[i]]);
		else
			Quer.push_back({z[i], i});
	}
	
	for (int i=1;i<=m;i++){
		if (seen[i] == 0)
			vec.push_back({c[i], i});
	}

	sort(rbegin(Quer), rend(Quer));
	sort(rbegin(vec), rend(vec));

	for (int i=1;i<=n;i++)
		Par[i] = Par[0], Sz[i] = 1;

	for (int i=0, id = 0;i<=vec.size();i++){
		while (id < Quer.size() and (i == vec.size() or vec[i].first < Quer[id].first)){
			int i1 = Quer[id].second;
			stack<pair<int,int>> stk;
			for (int j=1;j<i1;j++){
				if (x[j] == 1)
					lst[y[j]] = j;
			}

			for (int j=1;j<i1;j++){
				if (x[j] == 2 or z[j] < Quer[id].first or lst[y[j]] != j)
					continue;
				int A = root(a[y[j]]), B = root(b[y[j]]);
				if (Sz[A] < Sz[B])
					swap(A, B);
				if (A != B)
					Par[B].push(A), Sz[A] += Sz[B], stk.push({A, B});
			}
			for (int j=i1;j<=q;j++){
				if (x[j] == 2 or seen[y[j]] != j or c[y[j]] < z[i1])
					continue;
				int A = root(a[y[j]]), B = root(b[y[j]]);

				if (Sz[A] < Sz[B])
					swap(A, B);
				if (A != B)
					Par[B].push(A), Sz[A] += Sz[B], stk.push({A, B});
			}
			Ans[i1] = Sz[root(y[i1])], id++;
			
			while (stk.size() > 0){
				auto [A, B] = stk.top();
				stk.pop();
				Par[B].pop();
				Sz[A] -= Sz[B];
			}
		}
		
		if (i < vec.size()){
			int A = root(a[vec[i].second]), B = root(b[vec[i].second]);

			if (A != B and Sz[A] > Sz[B])
				Par[B].push(A), Sz[A] += Sz[B];
			else if (A != B)
				Par[A].push(B), Sz[B] += Sz[A];
		}
	}

	for (int i=1;i<=q;i++){
		seen[y[i]] = 0;
		if (x[i] == 2)
			cout<<Ans[i]<<'\n';
		else
			c[y[i]] = z[i];
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m, q;
	cin>>n>>m;

	for (int i=1;i<=m;i++)
		cin>>a[i]>>b[i]>>c[i];
	
	cin>>q;

	while (q > 0){
		for (int i=1;i<=min(q, K);i++)
			cin>>x[i]>>y[i]>>z[i];

		solve(n, m, min(q, K));
		q -= min(q, K);
	}

}

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