oj.uz

답안 #287864

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
287864 2020-09-01T05:17:30 Z 임성재(#5782) Election Campaign (JOI15_election_campaign) C++17
30 / 100
 1000 ms 68692 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];
vector<pii> upd[100010];
ll sum[100010][21];

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];
}

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

	return a;
}

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];
	sum[x][0] = Dp[x];

	for(auto i : upd[x]) {
		int k = i.fi;
		int u = i.se;

		sum[u][k] = sum[u][k-1] + sum[sp[u][k-1]][k-1] - dp[up(u, d[u] - d[sp[u][k-1]] - 1)];
	}

	for(auto i : qr[x]) {
		ll s = i.se;
		
		int u=i.fi.fi, v=i.fi.se;

		for(int j=20; j>=0; j--) {
			if(d[u] - d[x] >= (1 << j)) {
				s -= dp[up(u, d[u] - d[sp[u][j]] - 1)];
				s += sum[u][j];
				u = sp[u][j];
			}
		}

		for(int j=20; j>=0; j--) {
			if(d[v] - d[x] >= (1 << j)) {
				s -= dp[up(v, d[v] - d[sp[v][j]] - 1)];
				s += sum[v][j];
				v = sp[v][j];
			}
		}

		s += Dp[x];

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

	//cout << x << " " << dp[x] << " " << Dp[x] << endl;
}

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);
	}

	for(int i=1; i<=n; i++) {
		for(int j=1; j<=20; j++) {
			upd[sp[i][j]].eb(j, i);
		}
	}

	for(int i=1; i<=n; i++) sort(all(upd[i]));

	f(1);

	cout << dp[1];
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 6 ms 7936 KB Output is correct
5 Correct 239 ms 54224 KB Output is correct
6 Correct 366 ms 64720 KB Output is correct
7 Correct 671 ms 67280 KB Output is correct
8 Correct 165 ms 53180 KB Output is correct
9 Correct 642 ms 65560 KB Output is correct
10 Correct 159 ms 53692 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7552 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 7 ms 8064 KB Output is correct
4 Correct 495 ms 66900 KB Output is correct
5 Correct 511 ms 66752 KB Output is correct
6 Correct 437 ms 66772 KB Output is correct
7 Correct 502 ms 66900 KB Output is correct
8 Correct 502 ms 66816 KB Output is correct
9 Correct 440 ms 66900 KB Output is correct
10 Correct 492 ms 66772 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7552 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 7 ms 8064 KB Output is correct
4 Correct 495 ms 66900 KB Output is correct
5 Correct 511 ms 66752 KB Output is correct
6 Correct 437 ms 66772 KB Output is correct
7 Correct 502 ms 66900 KB Output is correct
8 Correct 502 ms 66816 KB Output is correct
9 Correct 440 ms 66900 KB Output is correct
10 Correct 492 ms 66772 KB Output is correct
11 Correct 23 ms 8448 KB Output is correct
12 Correct 511 ms 66776 KB Output is correct
13 Correct 505 ms 66824 KB Output is correct
14 Correct 451 ms 66772 KB Output is correct
15 Correct 519 ms 66904 KB Output is correct
16 Correct 475 ms 66772 KB Output is correct
17 Correct 525 ms 66800 KB Output is correct
18 Correct 504 ms 66772 KB Output is correct
19 Correct 442 ms 66852 KB Output is correct
20 Correct 503 ms 66776 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 372 ms 55428 KB Output is correct
2 Correct 438 ms 66772 KB Output is correct
3 Execution timed out 1018 ms 68692 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 6 ms 7936 KB Output is correct
5 Correct 239 ms 54224 KB Output is correct
6 Correct 366 ms 64720 KB Output is correct
7 Correct 671 ms 67280 KB Output is correct
8 Correct 165 ms 53180 KB Output is correct
9 Correct 642 ms 65560 KB Output is correct
10 Correct 159 ms 53692 KB Output is correct
11 Correct 7 ms 7936 KB Output is correct
12 Correct 8 ms 8064 KB Output is correct
13 Correct 8 ms 8064 KB Output is correct
14 Correct 7 ms 8188 KB Output is correct
15 Correct 7 ms 8060 KB Output is correct
16 Correct 8 ms 8064 KB Output is correct
17 Correct 7 ms 8060 KB Output is correct
18 Correct 8 ms 8064 KB Output is correct
19 Correct 7 ms 8060 KB Output is correct
20 Correct 8 ms 8064 KB Output is correct

Subtask #6
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7424 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7424 KB Output is correct
4 Correct 6 ms 7936 KB Output is correct
5 Correct 239 ms 54224 KB Output is correct
6 Correct 366 ms 64720 KB Output is correct
7 Correct 671 ms 67280 KB Output is correct
8 Correct 165 ms 53180 KB Output is correct
9 Correct 642 ms 65560 KB Output is correct
10 Correct 159 ms 53692 KB Output is correct
11 Correct 5 ms 7552 KB Output is correct
12 Correct 5 ms 7424 KB Output is correct
13 Correct 7 ms 8064 KB Output is correct
14 Correct 495 ms 66900 KB Output is correct
15 Correct 511 ms 66752 KB Output is correct
16 Correct 437 ms 66772 KB Output is correct
17 Correct 502 ms 66900 KB Output is correct
18 Correct 502 ms 66816 KB Output is correct
19 Correct 440 ms 66900 KB Output is correct
20 Correct 492 ms 66772 KB Output is correct
21 Correct 23 ms 8448 KB Output is correct
22 Correct 511 ms 66776 KB Output is correct
23 Correct 505 ms 66824 KB Output is correct
24 Correct 451 ms 66772 KB Output is correct
25 Correct 519 ms 66904 KB Output is correct
26 Correct 475 ms 66772 KB Output is correct
27 Correct 525 ms 66800 KB Output is correct
28 Correct 504 ms 66772 KB Output is correct
29 Correct 442 ms 66852 KB Output is correct
30 Correct 503 ms 66776 KB Output is correct
31 Correct 372 ms 55428 KB Output is correct
32 Correct 438 ms 66772 KB Output is correct
33 Execution timed out 1018 ms 68692 KB Time limit exceeded
34 Halted 0 ms 0 KB -