Submission #977145

#	Time	Username	Problem	Language	Result	Execution time	Memory
977145		dubabuba	Bridges (APIO19_bridges)	C++14	14 / 100	297 ms	10308 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int mxn = 4e5 + 10;
int par[mxn], ans[mxn], n, m;
vector<pair<int, pii>> edges;

int parent(int u) {
	if(par[u] < 0) return u;
	return par[u] = parent(par[u]);
}

bool unite(int u, int v) {
	u = parent(u);
	v = parent(v);
	if(u == v) return 0;

	if(par[u] > par[v]) swap(u, v);
	par[u] += par[v];
	par[v] = u;
	return 0;
}

int main() {
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		edges.push_back(MP(w, MP(u, v)));
	}

	int q;
	cin >> q;
	for(int i = 1; i <= q; i++) {
		int t, s, w;
		cin >> t >> s >> w;
		edges.push_back(MP(w, MP(-i, s)));
	}

	sort(edges.begin(), edges.end(), [&](const pair<int, pii> &L, const pair<int, pii> &R) { return L > R; });
	memset(par, -1, sizeof par);

	for(auto p : edges) {
		if(p.ss.ff > 0) {
			int w = p.ff;
			int u = p.ss.ff;
			int v = p.ss.ss;
			// cout << "unite: " << u << ' ' << v << endl;
			unite(u, v);
		}
		else {
			int w = p.ff;
			int i = -p.ss.ff;
			int s = p.ss.ss;

			int u = parent(s);
			assert(0 < i && i < mxn);
			assert(0 < u && u < mxn);
			ans[i] = -par[u];
			// cout << " start: " << s << ' ' << w << " = " << ans[i] << endl;
		}
	}

	for(int i = 1; i <= q; i++)
		cout << ans[i] << endl;
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:50:8: warning: unused variable 'w' [-Wunused-variable]
   50 |    int w = p.ff;
      |        ^
bridges.cpp:57:8: warning: unused variable 'w' [-Wunused-variable]
   57 |    int w = p.ff;
      |        ^

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