Submission #558738

#	Time	Username	Problem	Language	Result	Execution time	Memory
558738		heavylightdecomp	Bridges (APIO19_bridges)	C++14	14 / 100	268 ms	36992 KiB

bridges

#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;
	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;
			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(d,u,v) = 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';
	}
}

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