답안 #72790 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72790	2018-08-27T00:23:29 Z	shoemakerjo	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	784 ms	31696 KB

election_campaign

#include <bits/stdc++.h>

using namespace std;

#define maxn 100010

int dfsnum = 0;
int loc[maxn]; //store location in pre-order thing
int dep[maxn];

int N, M;
vector<vector<int>> adj(maxn);
int par[18][maxn]; //lca jump table

int a[maxn], b[maxn], c[maxn]; //query stuff
vector<vector<int>> quers(maxn); //queries stored at this node (i.e. I am the LCA)
int subsize[maxn]; //for hld thing
int head[maxn];

void dfs(int u, int p) {
	dep[u] = p == -1 ? 1 : dep[p] + 1;
	par[0][u] = p;
	subsize[u] = 1;
	for (int v : adj[u]) {
		if (v == p) continue;
		dfs(v, u);
		subsize[u] += subsize[v];
	}

}

int walk(int u, int k) {
	for (int i = 17; i >= 0; i--) {
		if (k & (1 << i)) {
			u = par[i][u];
		}
	}
	return u;
}

int lca(int u, int v) {
	if (dep[u] < dep[v]) return lca(v, u);
	u = walk(u, dep[u]-dep[v]);
	if (u == v) return u;
	for (int i = 17; i >= 0; i--) {
		if (par[i][u] != par[i][v]) {
			u = par[i][u];
			v = par[i][v];
		}
	}
	return par[0][u];
}

void dfs2(int u, int p, int h) {
	head[u] = h;
	loc[u] = ++dfsnum;
	for (int v : adj[u]) {
		if (v == p) continue;
		if (subsize[v] > (subsize[u]-1)/2) {
			dfs2(v, u, h);
		}
	}
	for (int v : adj[u]) {
		if (v == p) continue;
		if (subsize[v] > (subsize[u]-1)/2) continue;
		dfs2(v, u, v); //new head thing
	}
}

int seg[2][maxn*4];

int qu(int qs, int qe, int ss, int se, int si, int indo) {
	if (qs > qe || ss > se || qs > se || qe < ss) return 0;
	if (qs <= ss && se <= qe) return seg[indo][si];
	int mid = (ss + se)/2;
	return qu(qs, qe, ss, mid, si*2+1, indo) + 
		qu(qs, qe, mid+1, se, si*2+2, indo);
}

int query(int ss, int se, int indo) {
	return qu(ss, se, 1, N, 0, indo);
}

void up(int spot, int val, int ss, int se, int si, int indo) {
	if (ss == se) {
		seg[indo][si] += val;
		return;
	}
	int mid = (ss+se)/2;
	if (spot <= mid) {
		up(spot, val, ss, mid, si*2+1, indo);
	}
	else up(spot, val, mid+1, se, si*2+2, indo);
	seg[indo][si] = seg[indo][si*2+1] + seg[indo][si*2+2];
}

void update(int spot, int val, int indo) {
	up(spot, val, 1, N, 0, indo);
}

int dp[maxn];
int chsum[maxn]; //sum of dp for my children

int queryup(int lo, int hi, int indo) {

	int res = 0;
	while (lo != hi) {
		int ch = head[lo];
		if (dep[ch] <= dep[hi]) {
			ch = walk(lo, dep[lo]-dep[hi]-1);
		}
		res += query(loc[ch], loc[lo], indo);
		lo = par[0][ch];
	}

	return res;

}

void dfsdp(int u, int p) {
	for (int v : adj[u]) {
		if (v == p) continue;
		dfsdp(v, u);
		chsum[u] += dp[v];
	}
	update(loc[u], chsum[u], 1);
	dp[u] = chsum[u]; //one easy way to do it
	for (int k : quers[u]) {

		int ai = a[k];
		int bi = b[k];
		int ci = c[k];

		int tmp = 0; //temporary value
		tmp += queryup(ai, u, 1);
		tmp += queryup(bi, u, 1);

		tmp -= queryup(ai, u, 0);
		tmp -= queryup(bi, u, 0);



		tmp += chsum[u];
		tmp += ci;
		dp[u] = max(dp[u], tmp);
	}

	update(loc[u], dp[u], 0);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	int x, y;
	for (int i = 0; i < N-1; i++) {
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	dfs(1, -1);
	for (int i = 1; i < 18; i++) {
		for (int u = 1; u <= N; u++) {
			if (par[i-1][u] != -1) {
				par[i][u] = par[i-1][par[i-1][u]];
			}
			else par[i][u] = -1;
		}
	}
	dfs2(1, -1, 1);

	cin >> M;
	for (int i = 1; i <= M; i++) {
		cin >> a[i] >> b[i] >> c[i];
		quers[lca(a[i], b[i])].push_back(i);
	}

	dfsdp(1, -1);
	cout << dp[1] << endl;
	cout.flush();
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5240 KB	Output is correct
2	Correct	8 ms	5300 KB	Output is correct
3	Correct	6 ms	5336 KB	Output is correct
4	Correct	6 ms	5468 KB	Output is correct
5	Correct	154 ms	19976 KB	Output is correct
6	Correct	88 ms	29320 KB	Output is correct
7	Correct	136 ms	29320 KB	Output is correct
8	Correct	124 ms	29320 KB	Output is correct
9	Correct	148 ms	29320 KB	Output is correct
10	Correct	116 ms	29320 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	29320 KB	Output is correct
2	Correct	5 ms	29320 KB	Output is correct
3	Correct	7 ms	29320 KB	Output is correct
4	Correct	357 ms	31572 KB	Output is correct
5	Correct	260 ms	31588 KB	Output is correct
6	Correct	208 ms	31588 KB	Output is correct
7	Correct	257 ms	31588 KB	Output is correct
8	Correct	259 ms	31588 KB	Output is correct
9	Correct	207 ms	31588 KB	Output is correct
10	Correct	251 ms	31588 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	29320 KB	Output is correct
2	Correct	5 ms	29320 KB	Output is correct
3	Correct	7 ms	29320 KB	Output is correct
4	Correct	357 ms	31572 KB	Output is correct
5	Correct	260 ms	31588 KB	Output is correct
6	Correct	208 ms	31588 KB	Output is correct
7	Correct	257 ms	31588 KB	Output is correct
8	Correct	259 ms	31588 KB	Output is correct
9	Correct	207 ms	31588 KB	Output is correct
10	Correct	251 ms	31588 KB	Output is correct
11	Correct	27 ms	31588 KB	Output is correct
12	Correct	258 ms	31588 KB	Output is correct
13	Correct	259 ms	31588 KB	Output is correct
14	Correct	219 ms	31640 KB	Output is correct
15	Correct	272 ms	31640 KB	Output is correct
16	Correct	221 ms	31696 KB	Output is correct
17	Correct	264 ms	31696 KB	Output is correct
18	Correct	261 ms	31696 KB	Output is correct
19	Correct	230 ms	31696 KB	Output is correct
20	Correct	275 ms	31696 KB	Output is correct

Subtask #4
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	733 ms	31696 KB	Output is correct
2	Correct	225 ms	31696 KB	Output is correct
3	Correct	491 ms	31696 KB	Output is correct
4	Correct	344 ms	31696 KB	Output is correct
5	Correct	359 ms	31696 KB	Output is correct
6	Correct	349 ms	31696 KB	Output is correct
7	Correct	494 ms	31696 KB	Output is correct
8	Correct	430 ms	31696 KB	Output is correct
9	Correct	219 ms	31696 KB	Output is correct
10	Correct	572 ms	31696 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5240 KB	Output is correct
2	Correct	8 ms	5300 KB	Output is correct
3	Correct	6 ms	5336 KB	Output is correct
4	Correct	6 ms	5468 KB	Output is correct
5	Correct	154 ms	19976 KB	Output is correct
6	Correct	88 ms	29320 KB	Output is correct
7	Correct	136 ms	29320 KB	Output is correct
8	Correct	124 ms	29320 KB	Output is correct
9	Correct	148 ms	29320 KB	Output is correct
10	Correct	116 ms	29320 KB	Output is correct
11	Correct	9 ms	31696 KB	Output is correct
12	Correct	7 ms	31696 KB	Output is correct
13	Correct	10 ms	31696 KB	Output is correct
14	Correct	11 ms	31696 KB	Output is correct
15	Correct	8 ms	31696 KB	Output is correct
16	Correct	7 ms	31696 KB	Output is correct
17	Correct	8 ms	31696 KB	Output is correct
18	Correct	8 ms	31696 KB	Output is correct
19	Correct	7 ms	31696 KB	Output is correct
20	Correct	7 ms	31696 KB	Output is correct

Subtask #6
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5240 KB	Output is correct
2	Correct	8 ms	5300 KB	Output is correct
3	Correct	6 ms	5336 KB	Output is correct
4	Correct	6 ms	5468 KB	Output is correct
5	Correct	154 ms	19976 KB	Output is correct
6	Correct	88 ms	29320 KB	Output is correct
7	Correct	136 ms	29320 KB	Output is correct
8	Correct	124 ms	29320 KB	Output is correct
9	Correct	148 ms	29320 KB	Output is correct
10	Correct	116 ms	29320 KB	Output is correct
11	Correct	6 ms	29320 KB	Output is correct
12	Correct	5 ms	29320 KB	Output is correct
13	Correct	7 ms	29320 KB	Output is correct
14	Correct	357 ms	31572 KB	Output is correct
15	Correct	260 ms	31588 KB	Output is correct
16	Correct	208 ms	31588 KB	Output is correct
17	Correct	257 ms	31588 KB	Output is correct
18	Correct	259 ms	31588 KB	Output is correct
19	Correct	207 ms	31588 KB	Output is correct
20	Correct	251 ms	31588 KB	Output is correct
21	Correct	27 ms	31588 KB	Output is correct
22	Correct	258 ms	31588 KB	Output is correct
23	Correct	259 ms	31588 KB	Output is correct
24	Correct	219 ms	31640 KB	Output is correct
25	Correct	272 ms	31640 KB	Output is correct
26	Correct	221 ms	31696 KB	Output is correct
27	Correct	264 ms	31696 KB	Output is correct
28	Correct	261 ms	31696 KB	Output is correct
29	Correct	230 ms	31696 KB	Output is correct
30	Correct	275 ms	31696 KB	Output is correct
31	Correct	733 ms	31696 KB	Output is correct
32	Correct	225 ms	31696 KB	Output is correct
33	Correct	491 ms	31696 KB	Output is correct
34	Correct	344 ms	31696 KB	Output is correct
35	Correct	359 ms	31696 KB	Output is correct
36	Correct	349 ms	31696 KB	Output is correct
37	Correct	494 ms	31696 KB	Output is correct
38	Correct	430 ms	31696 KB	Output is correct
39	Correct	219 ms	31696 KB	Output is correct
40	Correct	572 ms	31696 KB	Output is correct
41	Correct	9 ms	31696 KB	Output is correct
42	Correct	7 ms	31696 KB	Output is correct
43	Correct	10 ms	31696 KB	Output is correct
44	Correct	11 ms	31696 KB	Output is correct
45	Correct	8 ms	31696 KB	Output is correct
46	Correct	7 ms	31696 KB	Output is correct
47	Correct	8 ms	31696 KB	Output is correct
48	Correct	8 ms	31696 KB	Output is correct
49	Correct	7 ms	31696 KB	Output is correct
50	Correct	7 ms	31696 KB	Output is correct
51	Correct	450 ms	31696 KB	Output is correct
52	Correct	265 ms	31696 KB	Output is correct
53	Correct	502 ms	31696 KB	Output is correct
54	Correct	275 ms	31696 KB	Output is correct
55	Correct	760 ms	31696 KB	Output is correct
56	Correct	276 ms	31696 KB	Output is correct
57	Correct	408 ms	31696 KB	Output is correct
58	Correct	350 ms	31696 KB	Output is correct
59	Correct	444 ms	31696 KB	Output is correct
60	Correct	270 ms	31696 KB	Output is correct
61	Correct	373 ms	31696 KB	Output is correct
62	Correct	398 ms	31696 KB	Output is correct
63	Correct	713 ms	31696 KB	Output is correct
64	Correct	260 ms	31696 KB	Output is correct
65	Correct	527 ms	31696 KB	Output is correct
66	Correct	276 ms	31696 KB	Output is correct
67	Correct	784 ms	31696 KB	Output is correct
68	Correct	273 ms	31696 KB	Output is correct
69	Correct	394 ms	31696 KB	Output is correct
70	Correct	348 ms	31696 KB	Output is correct

답안 #72790

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 5.0 / 5.0

Subtask #3 5.0 / 5.0

Subtask #4 30.0 / 30.0

Subtask #5 10.0 / 10.0

Subtask #6 40.0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
5.0 / 5.0

Subtask #3
5.0 / 5.0

Subtask #4
30.0 / 30.0

Subtask #5
10.0 / 10.0

Subtask #6
40.0 / 40.0