Submission #558736

#TimeUsernameProblemLanguageResultExecution timeMemory
558736heavylightdecomp다리 (APIO19_bridges)C++14
0 / 100
30 ms48072 KiB
#include<bits/stdc++.h>
using namespace std;
const int mxN = 500005, mxM = 1000005;
vector<tuple<int,int,int>> edges;
vector<pair<int,int>> queries[mxM];
int par[mxN], ccsz[mxN], ans[mxN];
int find(int x) { if(par[x]==x) return x; else return par[x] = find(par[x]); }
void merge(int a, int b) {a=find(a),b=find(b);if(a==b)return;par[a]=b; ccsz[b] += ccsz[a];}
signed main() {
	//freopen("bridge.in", "r", stdin);
	//freopen("bridge.out", "w", stdout);
	int n, m; cin >> n >> m;
	assert(n < 10000);
	for(int i = 1; i <= m; i++) {
		int u, v, d; cin >> u >> v >> d;
		edges.push_back({d,u,v});
	}
	for(int i = 0; i < mxN; i++) par[i] = i, ccsz[i] = 1;
	sort(edges.begin(), edges.end());
	int q; cin >> q;
	for(int g = 0; g < q; g++) {
		int t; cin >> t;
		if(t==1) {
			exit(-1);
			int b, r; cin >> b >> r;
		} else {
			int s, w; cin >> s >> w;
			assert(edges.size());
			auto lb = lower_bound(edges.begin(), edges.end(), make_tuple(w, LLONG_MIN, LLONG_MIN));
			assert((lb-edges.begin()) >= 0);
			queries[lb - edges.begin()].push_back({s,g});
		}
	}
	for(int i = 0; i < mxN; i++) ans[i] = 1;
	for(int e = (int(edges.size())) - 1; e >= 0; e--) {
		int u,v,d; tie(u,v,d) = edges[e];
		merge(u,v);
		for(int f = 0; f < int(queries[e].size()); f++) {
			int pos, oid; tie(pos, oid) = queries[e][f];
			int root = find(pos);
			assert(root >= 1 && root <= n);
			ans[oid] = ccsz[find(pos)];
		}
	}

	for(int g = 0; g < q; g++) {
		cout << ans[g] << '\n';
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...