답안 #72789 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72789	2018-08-27T00:22:44 Z	shoemakerjo	Election Campaign (JOI15_election_campaign)	C++14	20 / 100	617 ms	31760 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]/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	6 ms	5196 KB	Output is correct
2	Correct	6 ms	5224 KB	Output is correct
3	Correct	6 ms	5300 KB	Output is correct
4	Correct	6 ms	5528 KB	Output is correct
5	Correct	162 ms	20000 KB	Output is correct
6	Correct	86 ms	29268 KB	Output is correct
7	Correct	163 ms	29268 KB	Output is correct
8	Correct	132 ms	29268 KB	Output is correct
9	Correct	168 ms	29268 KB	Output is correct
10	Correct	171 ms	29268 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	29268 KB	Output is correct
2	Correct	6 ms	29268 KB	Output is correct
3	Correct	9 ms	29268 KB	Output is correct
4	Correct	311 ms	31664 KB	Output is correct
5	Correct	264 ms	31664 KB	Output is correct
6	Correct	214 ms	31664 KB	Output is correct
7	Correct	244 ms	31664 KB	Output is correct
8	Correct	247 ms	31760 KB	Output is correct
9	Correct	238 ms	31760 KB	Output is correct
10	Correct	244 ms	31760 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	29268 KB	Output is correct
2	Correct	6 ms	29268 KB	Output is correct
3	Correct	9 ms	29268 KB	Output is correct
4	Correct	311 ms	31664 KB	Output is correct
5	Correct	264 ms	31664 KB	Output is correct
6	Correct	214 ms	31664 KB	Output is correct
7	Correct	244 ms	31664 KB	Output is correct
8	Correct	247 ms	31760 KB	Output is correct
9	Correct	238 ms	31760 KB	Output is correct
10	Correct	244 ms	31760 KB	Output is correct
11	Correct	29 ms	31760 KB	Output is correct
12	Correct	253 ms	31760 KB	Output is correct
13	Correct	259 ms	31760 KB	Output is correct
14	Correct	223 ms	31760 KB	Output is correct
15	Correct	242 ms	31760 KB	Output is correct
16	Correct	225 ms	31760 KB	Output is correct
17	Correct	240 ms	31760 KB	Output is correct
18	Correct	248 ms	31760 KB	Output is correct
19	Correct	209 ms	31760 KB	Output is correct
20	Correct	266 ms	31760 KB	Output is correct

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	617 ms	31760 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5196 KB	Output is correct
2	Correct	6 ms	5224 KB	Output is correct
3	Correct	6 ms	5300 KB	Output is correct
4	Correct	6 ms	5528 KB	Output is correct
5	Correct	162 ms	20000 KB	Output is correct
6	Correct	86 ms	29268 KB	Output is correct
7	Correct	163 ms	29268 KB	Output is correct
8	Correct	132 ms	29268 KB	Output is correct
9	Correct	168 ms	29268 KB	Output is correct
10	Correct	171 ms	29268 KB	Output is correct
11	Incorrect	9 ms	31760 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #6
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5196 KB	Output is correct
2	Correct	6 ms	5224 KB	Output is correct
3	Correct	6 ms	5300 KB	Output is correct
4	Correct	6 ms	5528 KB	Output is correct
5	Correct	162 ms	20000 KB	Output is correct
6	Correct	86 ms	29268 KB	Output is correct
7	Correct	163 ms	29268 KB	Output is correct
8	Correct	132 ms	29268 KB	Output is correct
9	Correct	168 ms	29268 KB	Output is correct
10	Correct	171 ms	29268 KB	Output is correct
11	Correct	7 ms	29268 KB	Output is correct
12	Correct	6 ms	29268 KB	Output is correct
13	Correct	9 ms	29268 KB	Output is correct
14	Correct	311 ms	31664 KB	Output is correct
15	Correct	264 ms	31664 KB	Output is correct
16	Correct	214 ms	31664 KB	Output is correct
17	Correct	244 ms	31664 KB	Output is correct
18	Correct	247 ms	31760 KB	Output is correct
19	Correct	238 ms	31760 KB	Output is correct
20	Correct	244 ms	31760 KB	Output is correct
21	Correct	29 ms	31760 KB	Output is correct
22	Correct	253 ms	31760 KB	Output is correct
23	Correct	259 ms	31760 KB	Output is correct
24	Correct	223 ms	31760 KB	Output is correct
25	Correct	242 ms	31760 KB	Output is correct
26	Correct	225 ms	31760 KB	Output is correct
27	Correct	240 ms	31760 KB	Output is correct
28	Correct	248 ms	31760 KB	Output is correct
29	Correct	209 ms	31760 KB	Output is correct
30	Correct	266 ms	31760 KB	Output is correct
31	Incorrect	617 ms	31760 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

답안 #72789

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 5.0 / 5.0

Subtask #3 5.0 / 5.0

Subtask #4 0 / 30.0

Subtask #5 0 / 10.0

Subtask #6 0 / 40.0

Subtask #1
10.0 / 10.0

Subtask #2
5.0 / 5.0

Subtask #3
5.0 / 5.0

Subtask #4
0 / 30.0

Subtask #5
0 / 10.0

Subtask #6
0 / 40.0