Submission #1142594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142594		am_aadvik	Election Campaign (JOI15_election_campaign)	C++20	35 / 100	164 ms	30048 KiB

election_campaign

#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;

vector<int> g[100005];
int p[100005][20], dep[100005];
bool done[100005];

void dfs(int node, int par) {
	dep[node] = dep[par] + 1;
	p[node][0] = par;
	for (int i = 1; i < 20; ++i)
		p[node][i] = p[p[node][i - 1]][i - 1];
	for (auto x : g[node])
		if (x != par) dfs(x, node);
}

void fill(int node, int par) {
	if (done[node]) return;
	done[node] = 1;
	for (auto x : g[node])
		if (x != par) fill(x, node);
}

int kpar(int u, int k) {
	for (int i = 0; i < 20; ++i)
		if (k & (1 << i))
			u = p[u][i];
	return u;
}

int lca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	u = kpar(u, dep[u] - dep[v]);
	if (u == v) return u;
	for (int i = 19; i >= 0; --i)
		if (p[u][i] != p[v][i])
			u = p[u][i], v = p[v][i];
	return p[u][0];
}

int main()
{
	int n; cin >> n;
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	dfs(1, 0);
	int m; cin >> m;
	vector<vector<int>> q, a;
	while (m--) {
		int x, y, z; cin >> x >> y >> z;
		q.push_back({ x,y,z });
		int lc = lca(x, y);
		a.push_back({ -dep[lc], lc, (int)q.size() - 1 });
	}
	sort(a.begin(), a.end());

	int ans = 0;
	for (auto x : a) {
		int u = q[x[2]][0], v = q[x[2]][1];
		if (done[u] || done[v]) continue;
		++ans, fill(x[1], p[x[1]][0]);
	}
	cout << ans;
}

• Subtask 1: 0 / 10
• Subtask 2: 5 / 5
• Subtask 3: 0 / 5
• Subtask 4: 30 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40