Submission #915075

#	Time	Username	Problem	Language	Result	Execution time	Memory
915075		yellowtoad	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	220 ms	39576 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));
}

int sum(int u, int v) {
	if (d[u] < d[v]) return 0;
	if (group[u].f == group[v].f) return ps[group[v].f][group[v].s]-ps[group[u].f][group[u].s+1];
	return ps[group[u].f][0]-ps[group[u].f][group[u].s+1]+sum(p[grp[group[u].f][0]][0],v);
}

int summ(int u, int v) {
	if (d[u] < d[v]) return 0;
	if (group[u].f == group[v].f) return pss[group[v].f][group[v].s]-pss[group[u].f][group[u].s+1];
	return pss[group[u].f][0]-pss[group[u].f][group[u].s+1]+summ(p[grp[group[u].f][0]][0],v);
}

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];
	pss[group[u].f][group[u].s] = pss[group[u].f][group[u].s+1];
	int tmp = dp[u];
	for (int i = 0; i < add[u].size(); i++) dp[u] = max(dp[u],add[u][i].s+sum(add[u][i].f.f,u)-summ(add[u][i].f.f,u)+sum(add[u][i].f.s,u)-summ(add[u][i].f.s,u)-tmp);
	pss[group[u].f][group[u].s] += 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);
	dfs(1,0);
	cout << dp[1] << 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:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for (int i = 0; i < edge[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~
election_campaign.cpp:74: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]
   74 |  for (int i = 0; i < add[u].size(); i++) dp[u] = max(dp[u],add[u][i].s+sum(add[u][i].f.f,u)-summ(add[u][i].f.f,u)+sum(add[u][i].f.s,u)-summ(add[u][i].f.s,u)-tmp);
      |                  ~~^~~~~~~~~~~~~~~

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