oj.uz

Submission #287854

# Submission time Handle Problem Language Result Execution time Memory
287854 2020-09-01T04:51:50 Z 임성재(#5782) Election Campaign (JOI15_election_campaign) C++17
20 / 100
 1000 ms 28540 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

int n, m;
vector<int> g[100010];
int d[100010];
int sp[100010][21];
ll dp[100010];
ll Dp[100010];
vector<pair<pii, int>> qr[100010];

void dfs(int x) {
	for(int i=1; i<=20; i++) 
		sp[x][i] = sp[sp[x][i-1]][i-1];

	for(auto i : g[x]) {
		if(i == sp[x][0]) continue;
		
		d[i] = d[x] + 1;
		sp[i][0] = x;
		
		dfs(i);
	}
}

int lca(int a, int b) {
	if(d[a] > d[b]) swap(a, b);

	for(int i=20; i>=0; i--) {
		if(d[b] - d[a] >= (1<<i)) {
			b = sp[b][i];
		}
	}

	if(a == b) return a;

	for(int i=20; i>=0; i--) {
		if(sp[a][i] != sp[b][i]) {
			a = sp[a][i];
			b = sp[b][i];
		}
	}

	return sp[a][0];
}

void f(int x) {
	for(auto i : g[x]) {
		if(i == sp[x][0]) continue;

		f(i);

		Dp[x] += dp[i];
	}

	dp[x] = Dp[x];

	for(auto i : qr[x]) {
		ll sum = i.se;
		
		int u=0, v=0;
		for(int j=i.fi.fi; j != x; j = sp[j][0]) {
			for(auto k : g[j]) {
				if(k == sp[j][0] || k == u)  continue;

				sum += dp[k];
			}
			u = j;
		}

		for(int j=i.fi.se; j != x; j = sp[j][0]) {
			for(auto k : g[j]) {
				if(k == sp[j][0] || k == v) continue;

				sum += dp[k];
			}
			v = j;
		}

		for(auto i : g[x]) {
			if(i == sp[i][0] || i == u || i == v) continue;
			sum += dp[i];
		}

		dp[x] = max(dp[x], sum);
	}
}

int main() {
	fast;

	cin >> n;

	for(int i=1; i<n; i++) {
		int u, v;
		cin >> u >> v;

		g[u].eb(v);
		g[v].eb(u);
	}

	dfs(1);

	cin >> m;
	for(int i=0; i<m; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		if(d[a] > d[b]) swap(a, b);

		qr[lca(a, b)].eb(mp(a, b), c);
	}

	f(1);

	cout << dp[1];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 5 ms 5248 KB Output is correct
5 Correct 114 ms 18740 KB Output is correct
6 Correct 60 ms 26360 KB Output is correct
7 Correct 145 ms 23672 KB Output is correct
8 Correct 94 ms 18424 KB Output is correct
9 Correct 166 ms 22140 KB Output is correct
10 Correct 81 ms 18296 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 4 ms 5248 KB Output is correct
4 Execution timed out 1090 ms 28392 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 4 ms 5248 KB Output is correct
4 Execution timed out 1090 ms 28392 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 20272 KB Output is correct
2 Execution timed out 1095 ms 28540 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 5 ms 5248 KB Output is correct
5 Correct 114 ms 18740 KB Output is correct
6 Correct 60 ms 26360 KB Output is correct
7 Correct 145 ms 23672 KB Output is correct
8 Correct 94 ms 18424 KB Output is correct
9 Correct 166 ms 22140 KB Output is correct
10 Correct 81 ms 18296 KB Output is correct
11 Correct 5 ms 5248 KB Output is correct
12 Correct 7 ms 5248 KB Output is correct
13 Correct 5 ms 5248 KB Output is correct
14 Correct 6 ms 5248 KB Output is correct
15 Correct 5 ms 5248 KB Output is correct
16 Correct 5 ms 5248 KB Output is correct
17 Correct 5 ms 5248 KB Output is correct
18 Correct 7 ms 5248 KB Output is correct
19 Correct 5 ms 5248 KB Output is correct
20 Correct 6 ms 5248 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 5 ms 5248 KB Output is correct
5 Correct 114 ms 18740 KB Output is correct
6 Correct 60 ms 26360 KB Output is correct
7 Correct 145 ms 23672 KB Output is correct
8 Correct 94 ms 18424 KB Output is correct
9 Correct 166 ms 22140 KB Output is correct
10 Correct 81 ms 18296 KB Output is correct
11 Correct 4 ms 4992 KB Output is correct
12 Correct 3 ms 5120 KB Output is correct
13 Correct 4 ms 5248 KB Output is correct
14 Execution timed out 1090 ms 28392 KB Time limit exceeded
15 Halted 0 ms 0 KB -