제출 #1204475

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1204475		PlayVoltz	Bridges (APIO19_bridges)	C++20	100 / 100	1659 ms	298568 KiB

bridges

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

const int BLK = 1000;

struct trio{
	int a, b, c;
};

vector<trio> quer;
stack<int> del;
vector<int> dsu, sz;

int fp(int a){
	if (dsu[a]==-1)return a;
	return fp(dsu[a]);
}

void merge(int a, int b){
	a=fp(a), b=fp(b);
	if (a==b)return;
	if (sz[a]>sz[b])swap(a, b);
	sz[b]+=sz[a];
	dsu[a]=b;
	del.push(a);
}

void undo(int k){
	while (k--){
		int a=del.top();
		del.pop();
		sz[dsu[a]]-=sz[a];
		dsu[a]=-1;
	}
}

bool custom(trio a, trio b){
	return a.c>b.c;
}

bool custom2(int a, int b){
	return quer[a].c>quer[b].c;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m, q;
	cin>>n>>m;
	vector<trio> edges(m);
	for (int i=0; i<m; ++i)cin>>edges[i].a>>edges[i].b>>edges[i].c;
	cin>>q;
	vector<int> ans(q, -1);
	quer.resize(q);
	vector<vector<int> > add(q);
	for (int i=0; i<q; ++i)cin>>quer[i].a>>quer[i].b>>quer[i].c, --quer[i].b;
	for (int l=0, r=min(BLK, q); l<q; l+=BLK, r=min(r+BLK, q)){
		dsu.assign(n+1, -1);
		sz.assign(n+1, 1);
		vector<bool> change(m+1, 0);
		vector<int> queries, changed;
		for (int i=l; i<r; ++i)if (quer[i].a==1)change[quer[i].b]=1, changed.pb(quer[i].b);
		vector<trio> vect;
		for (int i=0; i<m; ++i)if (!change[i])vect.pb(edges[i]);
		sort(vect.begin(), vect.end(), custom);
		for (int i=l; i<r; ++i){
			if (quer[i].a==1)edges[quer[i].b].c=quer[i].c;
			else{
				queries.pb(i);
				for (auto a:changed)if (edges[a].c>=quer[i].c)add[i].pb(a);
			}
		}
		sort(queries.begin(), queries.end(), custom2);
		int p=0;
		for (auto c:queries){
			while (p<vect.size()&&vect[p].c>=quer[c].c)merge(vect[p].a, vect[p].b), ++p;
			int temp=del.size();
			for (auto a:add[c])merge(edges[a].a, edges[a].b);
			ans[c]=sz[fp(quer[c].b+1)];
			undo(del.size()-temp);
		}
	}
	for (auto a:ans)if (a!=-1)cout<<a<<"\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