제출 #983720

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
983720		pcc	다리 (APIO19_bridges)	C++17	0 / 100	36 ms	4116 KiB

bridges

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 2e5+10;
const int lim = 3030;
int N,M,Q;
vector<pair<int,pii>> edges;
pair<int,pii> req[mxn];

struct DSU{
	int dsu[mxn],sz[mxn];
	DSU(){}
	void init(int n){
		for(int i = 0;i<n;i++)dsu[i] = i,sz[i] = 1;
		return;
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		a = root(a),b = root(b);
		if(a == b)return;
		if(sz[a]<sz[b])swap(a,b);
		dsu[b] = a;
		sz[a] += sz[b];
	}
};

namespace S1{
	DSU dsu;
	void GO(){
		for(int i = 0;i<Q;i++){
			if(req[i].fs == 1){
				int id = req[i].sc.fs,w = req[i].sc.sc;
				edges[id-1].fs = w;
			}
			else{
				dsu.init(N+1);
				for(auto &j:edges){
					if(j.fs>=req[i].sc.sc)dsu.onion(j.sc.fs,j.sc.sc);
				}
				cout<<dsu.sz[dsu.root(req[i].sc.fs)]<<'\n';
			}
		}
		return;
	}
}

namespace S2{
	void GO(){
	}
}

namespace S3{
	void GO(){
	}
}


int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	bool flag = false;
	for(int i = 0;i<M;i++){
		int a,b,c;
		cin>>a>>b>>c;
		edges.push_back(make_pair(c,pii(a,b)));
	}
	cin>>Q;
	for(int i = 0;i<Q;i++){
		int t,a,b;
		cin>>t>>a>>b;
		req[i] = make_pair(t,pii(a,b));
		if(t == 1)flag = true;
	}
	if(N<=lim&&M<=lim&&Q<=lim)S1::GO();
	else if(flag)S2::GO();
	else S3::GO();
	return 0;
}

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