oj.uz

Submission #915075

# Submission time Handle Problem Language Result Execution time Memory
915075 2024-01-23T09:57:30 Z yellowtoad Election Campaign (JOI15_election_campaign) C++17
100 / 100
 220 ms 39576 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 93 ms 29352 KB Output is correct
6 Correct 43 ms 30012 KB Output is correct
7 Correct 74 ms 30064 KB Output is correct
8 Correct 90 ms 36692 KB Output is correct
9 Correct 72 ms 28536 KB Output is correct
10 Correct 76 ms 36708 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 3 ms 8792 KB Output is correct
4 Correct 100 ms 33340 KB Output is correct
5 Correct 98 ms 33124 KB Output is correct
6 Correct 92 ms 33224 KB Output is correct
7 Correct 94 ms 33356 KB Output is correct
8 Correct 96 ms 33344 KB Output is correct
9 Correct 89 ms 33216 KB Output is correct
10 Correct 96 ms 33088 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 3 ms 8792 KB Output is correct
4 Correct 100 ms 33340 KB Output is correct
5 Correct 98 ms 33124 KB Output is correct
6 Correct 92 ms 33224 KB Output is correct
7 Correct 94 ms 33356 KB Output is correct
8 Correct 96 ms 33344 KB Output is correct
9 Correct 89 ms 33216 KB Output is correct
10 Correct 96 ms 33088 KB Output is correct
11 Correct 10 ms 9564 KB Output is correct
12 Correct 99 ms 33484 KB Output is correct
13 Correct 106 ms 33636 KB Output is correct
14 Correct 96 ms 33792 KB Output is correct
15 Correct 104 ms 33472 KB Output is correct
16 Correct 93 ms 33528 KB Output is correct
17 Correct 98 ms 33596 KB Output is correct
18 Correct 96 ms 33432 KB Output is correct
19 Correct 98 ms 33632 KB Output is correct
20 Correct 96 ms 33596 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 31840 KB Output is correct
2 Correct 88 ms 33260 KB Output is correct
3 Correct 144 ms 33016 KB Output is correct
4 Correct 137 ms 38964 KB Output is correct
5 Correct 168 ms 32492 KB Output is correct
6 Correct 185 ms 39120 KB Output is correct
7 Correct 165 ms 32224 KB Output is correct
8 Correct 174 ms 32868 KB Output is correct
9 Correct 90 ms 33220 KB Output is correct
10 Correct 142 ms 31240 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 93 ms 29352 KB Output is correct
6 Correct 43 ms 30012 KB Output is correct
7 Correct 74 ms 30064 KB Output is correct
8 Correct 90 ms 36692 KB Output is correct
9 Correct 72 ms 28536 KB Output is correct
10 Correct 76 ms 36708 KB Output is correct
11 Correct 3 ms 9052 KB Output is correct
12 Correct 3 ms 8848 KB Output is correct
13 Correct 4 ms 9052 KB Output is correct
14 Correct 3 ms 9076 KB Output is correct
15 Correct 3 ms 9052 KB Output is correct
16 Correct 3 ms 8936 KB Output is correct
17 Correct 3 ms 9052 KB Output is correct
18 Correct 3 ms 8796 KB Output is correct
19 Correct 3 ms 9052 KB Output is correct
20 Correct 3 ms 8796 KB Output is correct

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 93 ms 29352 KB Output is correct
6 Correct 43 ms 30012 KB Output is correct
7 Correct 74 ms 30064 KB Output is correct
8 Correct 90 ms 36692 KB Output is correct
9 Correct 72 ms 28536 KB Output is correct
10 Correct 76 ms 36708 KB Output is correct
11 Correct 2 ms 8792 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct
13 Correct 3 ms 8792 KB Output is correct
14 Correct 100 ms 33340 KB Output is correct
15 Correct 98 ms 33124 KB Output is correct
16 Correct 92 ms 33224 KB Output is correct
17 Correct 94 ms 33356 KB Output is correct
18 Correct 96 ms 33344 KB Output is correct
19 Correct 89 ms 33216 KB Output is correct
20 Correct 96 ms 33088 KB Output is correct
21 Correct 10 ms 9564 KB Output is correct
22 Correct 99 ms 33484 KB Output is correct
23 Correct 106 ms 33636 KB Output is correct
24 Correct 96 ms 33792 KB Output is correct
25 Correct 104 ms 33472 KB Output is correct
26 Correct 93 ms 33528 KB Output is correct
27 Correct 98 ms 33596 KB Output is correct
28 Correct 96 ms 33432 KB Output is correct
29 Correct 98 ms 33632 KB Output is correct
30 Correct 96 ms 33596 KB Output is correct
31 Correct 220 ms 31840 KB Output is correct
32 Correct 88 ms 33260 KB Output is correct
33 Correct 144 ms 33016 KB Output is correct
34 Correct 137 ms 38964 KB Output is correct
35 Correct 168 ms 32492 KB Output is correct
36 Correct 185 ms 39120 KB Output is correct
37 Correct 165 ms 32224 KB Output is correct
38 Correct 174 ms 32868 KB Output is correct
39 Correct 90 ms 33220 KB Output is correct
40 Correct 142 ms 31240 KB Output is correct
41 Correct 3 ms 9052 KB Output is correct
42 Correct 3 ms 8848 KB Output is correct
43 Correct 4 ms 9052 KB Output is correct
44 Correct 3 ms 9076 KB Output is correct
45 Correct 3 ms 9052 KB Output is correct
46 Correct 3 ms 8936 KB Output is correct
47 Correct 3 ms 9052 KB Output is correct
48 Correct 3 ms 8796 KB Output is correct
49 Correct 3 ms 9052 KB Output is correct
50 Correct 3 ms 8796 KB Output is correct
51 Correct 168 ms 32896 KB Output is correct
52 Correct 102 ms 33388 KB Output is correct
53 Correct 173 ms 31664 KB Output is correct
54 Correct 138 ms 38944 KB Output is correct
55 Correct 213 ms 32460 KB Output is correct
56 Correct 103 ms 33648 KB Output is correct
57 Correct 167 ms 32248 KB Output is correct
58 Correct 148 ms 39340 KB Output is correct
59 Correct 157 ms 32920 KB Output is correct
60 Correct 97 ms 33596 KB Output is correct
61 Correct 144 ms 32180 KB Output is correct
62 Correct 144 ms 38832 KB Output is correct
63 Correct 201 ms 32432 KB Output is correct
64 Correct 98 ms 33492 KB Output is correct
65 Correct 147 ms 32340 KB Output is correct
66 Correct 137 ms 39576 KB Output is correct
67 Correct 195 ms 32396 KB Output is correct
68 Correct 96 ms 33548 KB Output is correct
69 Correct 143 ms 30828 KB Output is correct
70 Correct 160 ms 39568 KB Output is correct