Submission #1142591

#TimeUsernameProblemLanguageResultExecution timeMemory
1142591am_aadvikElection Campaign (JOI15_election_campaign)C++20
0 / 100
1094 ms29868 KiB
#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) {
	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;
}
#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...