oj.uz

Submission #156560

# Submission time Handle Problem Language Result Execution time Memory
156560 2019-10-06T13:59:01 Z Saboon Election Campaign (JOI15_election_campaign) C++14
10 / 100
 459 ms 35064 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;

vector<int> t[maxn], vec[maxn];
int dp[maxn], mx[maxn], c[maxn], lazy[maxn], cost[maxn], w[maxn];
set<int> s[maxn];

void dfs(int v, int p = -1){
	int sum = 0;
	for (auto u : t[v])
		if (u != p)
			dfs(u, v), sum += dp[u];
	dp[v] = sum + mx[v];
	for (auto u : t[v])
		if (u != p)
			lazy[c[u]] += sum - dp[u];
	for (auto u : t[v]){
		if (u != p){
			if (s[c[u]].size() > s[c[v]].size())
				swap(c[v], c[u]);
			for (auto idx : s[c[u]]){
				if (s[c[v]].find(idx) != s[c[v]].end())
					dp[v] = max(dp[v], cost[idx] + lazy[c[v]] + lazy[c[u]] - sum + w[idx]);
				else
					s[c[v]].insert(idx), cost[idx] += lazy[c[u]] - lazy[c[v]];
			}
			s[c[u]].clear();
		}
	}
	for (auto idx : vec[v]){
		if (s[c[v]].find(idx) == s[c[v]].end())
			s[c[v]].insert(idx), cost[idx] = sum - lazy[c[v]];
		else
			dp[v] = max(dp[v], cost[idx] + lazy[c[v]] + w[idx]);
	}
}

int main(){
	ios_base::sync_with_stdio (false);
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++){
		int v, u;
		cin >> v >> u;
//		v --, u --;
		t[v].push_back(u);
		t[u].push_back(v);
	}
	int m;
	cin >> m;
	for (int i = 1; i <= n; i++)
		c[i] = i;
	for (int i = 1; i <= m; i++){
		int v, u;
		cin >> v >> u >> w[i];
		if (v == u){
			mx[v] = max(mx[v], w[i]);
			continue;
		}
		vec[v].push_back(i);
		vec[u].push_back(i);
	}
	dfs(1);
	cout << dp[1] << endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Correct 10 ms 9720 KB Output is correct
3 Correct 10 ms 9848 KB Output is correct
4 Correct 11 ms 9848 KB Output is correct
5 Correct 84 ms 15352 KB Output is correct
6 Correct 61 ms 26056 KB Output is correct
7 Correct 71 ms 22400 KB Output is correct
8 Correct 61 ms 15708 KB Output is correct
9 Incorrect 82 ms 20216 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 10 ms 9720 KB Output is correct
3 Correct 11 ms 9948 KB Output is correct
4 Correct 222 ms 34600 KB Output is correct
5 Correct 214 ms 34660 KB Output is correct
6 Correct 210 ms 34552 KB Output is correct
7 Correct 211 ms 34552 KB Output is correct
8 Correct 217 ms 34660 KB Output is correct
9 Correct 200 ms 34596 KB Output is correct
10 Correct 210 ms 34524 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 10 ms 9720 KB Output is correct
3 Correct 11 ms 9948 KB Output is correct
4 Correct 222 ms 34600 KB Output is correct
5 Correct 214 ms 34660 KB Output is correct
6 Correct 210 ms 34552 KB Output is correct
7 Correct 211 ms 34552 KB Output is correct
8 Correct 217 ms 34660 KB Output is correct
9 Correct 200 ms 34596 KB Output is correct
10 Correct 210 ms 34524 KB Output is correct
11 Correct 36 ms 11768 KB Output is correct
12 Correct 216 ms 35036 KB Output is correct
13 Correct 211 ms 34808 KB Output is correct
14 Correct 202 ms 34936 KB Output is correct
15 Correct 252 ms 34968 KB Output is correct
16 Correct 205 ms 34916 KB Output is correct
17 Correct 223 ms 34980 KB Output is correct
18 Correct 219 ms 34808 KB Output is correct
19 Correct 211 ms 34860 KB Output is correct
20 Correct 224 ms 35064 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 459 ms 28756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Correct 10 ms 9720 KB Output is correct
3 Correct 10 ms 9848 KB Output is correct
4 Correct 11 ms 9848 KB Output is correct
5 Correct 84 ms 15352 KB Output is correct
6 Correct 61 ms 26056 KB Output is correct
7 Correct 71 ms 22400 KB Output is correct
8 Correct 61 ms 15708 KB Output is correct
9 Incorrect 82 ms 20216 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9848 KB Output is correct
2 Correct 10 ms 9720 KB Output is correct
3 Correct 10 ms 9848 KB Output is correct
4 Correct 11 ms 9848 KB Output is correct
5 Correct 84 ms 15352 KB Output is correct
6 Correct 61 ms 26056 KB Output is correct
7 Correct 71 ms 22400 KB Output is correct
8 Correct 61 ms 15708 KB Output is correct
9 Incorrect 82 ms 20216 KB Output isn't correct
10 Halted 0 ms 0 KB -