제출 #1281453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281453		Jawad_Akbar_JJ	다리 (APIO19_bridges)	C++20	100 / 100	1798 ms	5024 KiB

bridges

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

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

int root(int v){
	while (Par[v] != 0)
		v = Par[v];
	return v;
}

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

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

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

	for (auto [vl, i] : vec){
		if (i > 0){
			int A = root(a[i]), B = root(b[i]);

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

		int i1 = -i;
		stack<pair<int,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] < vl 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)
				stk.push({A, {B, Par[B]}}), Par[B] = A, Sz[A] += Sz[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)
				stk.push({A, {B, Par[B]}}), Par[B] = A, Sz[A] += Sz[B];
		}
		Ans[i1] = Sz[root(y[i1])];
		
		while (stk.size() > 0){
			auto [A, B] = stk.top();
			stk.pop();
			Par[B.first] = B.second;
			Sz[A] -= Sz[B.first];
		}
	}

	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: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27