Submission #915050

#	Time	Username	Problem	Language	Result	Execution time	Memory
915050		yellowtoad	Election Campaign (JOI15_election_campaign)	C++17	0 / 100	149 ms	32108 KiB

election_campaign

#include <iostream>
#include <vector>
#define f first
#define s second
using namespace std;

int n, m, p[100010][20], d[100010], sub[100010], dp[100010];
pair<int,int> group[100010];
vector<int> edge[100010];
vector<pair<pair<int,int>,int>> add[100010];
vector<vector<int>> grp, ps, pss;

void dfs1(int u, int v, int depth) {
	p[u][0] = v;
	d[u] = depth;
	sub[u] = 1;
	for (int i = 1; i < 20; i++) p[u][i] = p[p[u][i-1]][i-1];
	for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) dfs1(edge[u][i],u,depth+1), sub[u] += sub[edge[u][i]];
}

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

void hld(int u, int v, int newgrp) {
	if (newgrp) {
		grp.push_back({u});
		ps.push_back({0,0});
		pss.push_back({0,0});
		group[u] = {grp.size()-1,0};
	} else {
		grp[group[v].f].push_back(u);
		ps[group[v].f].push_back(0);
		pss[group[v].f].push_back(0);
		group[u] = {group[v].f,group[v].s+1};
	}
	for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) hld(edge[u][i],u,(sub[edge[u][i]] <= (sub[u]-1)/2));
}

void dfs(int u, int v) {
	for (int i = 0; i < edge[u].size(); i++) {
		if (edge[u][i] != v) {
			dfs(edge[u][i],u);
			dp[u] += dp[edge[u][i]];
		}
	}
	ps[group[u].f][group[u].s] = ps[group[u].f][group[u].s+1]+dp[u];
	for (int i = 0; i < add[u].size(); i++) {
		
	}
	pss[group[u].f][group[u].s] = pss[group[u].f][group[u].s+1]+dp[u];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs1(1,0,1);
	cin >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		add[lca(u,v)].push_back({{u,v},w});
	}
	hld(1,0,1);
	/*for (int i = 0; i < grp.size(); i++) {
		for (int j = 0; j < grp[i].size(); j++) cout << grp[i][j] << " ";
		cout << endl;
	}
	for (int i = 1; i <= n; i++) cout << group[i].f << " " << group[i].s << endl;*/
}

Compilation message (stderr)

election_campaign.cpp: In function 'void dfs1(int, int, int)':
election_campaign.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) dfs1(edge[u][i],u,depth+1), sub[u] += sub[edge[u][i]];
      |                  ~~^~~~~~~~~~~~~~~~
election_campaign.cpp: In function 'void hld(int, int, int)':
election_campaign.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for (int i = 0; i < edge[u].size(); i++) if (edge[u][i] != v) hld(edge[u][i],u,(sub[edge[u][i]] <= (sub[u]-1)/2));
      |                  ~~^~~~~~~~~~~~~~~~
election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for (int i = 0; i < edge[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~
election_campaign.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for (int i = 0; i < add[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~

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