oj.uz

Submission #72785

# Submission time Handle Problem Language Result Execution time Memory
72785 2018-08-27T00:18:18 Z shoemakerjo Election Campaign (JOI15_election_campaign) C++14
60 / 100
 1000 ms 31740 KB 
#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]/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) {
	// cout << endl << "going from " << lo << " to " << hi << endl;

	int res = 0;
	while (lo != hi) {
		int ch = head[lo];
		if (dep[ch] <= dep[hi]) {
			ch = walk(lo, dep[lo]-dep[hi]-1);
		}
		// cout << lo << " to " << ch << " is a section " << endl;
		res += query(loc[ch], loc[lo], indo);
		lo = par[0][ch];
	}

	// cout << "res: " << res << endl << endl;
	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];
		// cout << ai << " " << bi << " " << ci << '\n';

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

		// cout << "   after ch adds: " << tmp << '\n';
		tmp -= queryup(ai, u, 0);
		tmp -= queryup(bi, u, 0);



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

	// cout << u << ": " << dp[u] << " ch sum: " << chsum[u] << '\n';
	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];
		// cout << i << ": " << a[i] << " " << b[i] << " " << c[i] << endl;
		quers[lca(a[i], b[i])].push_back(i);
		// cout << a[i] << " " << b[i] << ": " << lca(a[i], b[i]) << '\n';
	}

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5348 KB Output is correct
3 Correct 6 ms 5400 KB Output is correct
4 Correct 7 ms 5408 KB Output is correct
5 Correct 209 ms 19984 KB Output is correct
6 Correct 93 ms 29292 KB Output is correct
7 Correct 174 ms 29292 KB Output is correct
8 Correct 126 ms 29292 KB Output is correct
9 Correct 161 ms 29292 KB Output is correct
10 Correct 113 ms 29292 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29292 KB Output is correct
2 Correct 6 ms 29292 KB Output is correct
3 Correct 6 ms 29292 KB Output is correct
4 Correct 270 ms 31596 KB Output is correct
5 Correct 243 ms 31724 KB Output is correct
6 Correct 224 ms 31740 KB Output is correct
7 Correct 239 ms 31740 KB Output is correct
8 Correct 236 ms 31740 KB Output is correct
9 Correct 208 ms 31740 KB Output is correct
10 Correct 237 ms 31740 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29292 KB Output is correct
2 Correct 6 ms 29292 KB Output is correct
3 Correct 6 ms 29292 KB Output is correct
4 Correct 270 ms 31596 KB Output is correct
5 Correct 243 ms 31724 KB Output is correct
6 Correct 224 ms 31740 KB Output is correct
7 Correct 239 ms 31740 KB Output is correct
8 Correct 236 ms 31740 KB Output is correct
9 Correct 208 ms 31740 KB Output is correct
10 Correct 237 ms 31740 KB Output is correct
11 Correct 28 ms 31740 KB Output is correct
12 Correct 236 ms 31740 KB Output is correct
13 Correct 332 ms 31740 KB Output is correct
14 Correct 201 ms 31740 KB Output is correct
15 Correct 251 ms 31740 KB Output is correct
16 Correct 200 ms 31740 KB Output is correct
17 Correct 234 ms 31740 KB Output is correct
18 Correct 288 ms 31740 KB Output is correct
19 Correct 273 ms 31740 KB Output is correct
20 Correct 355 ms 31740 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 920 ms 31740 KB Output is correct
2 Correct 202 ms 31740 KB Output is correct
3 Correct 446 ms 31740 KB Output is correct
4 Correct 376 ms 31740 KB Output is correct
5 Correct 330 ms 31740 KB Output is correct
6 Correct 325 ms 31740 KB Output is correct
7 Correct 470 ms 31740 KB Output is correct
8 Correct 418 ms 31740 KB Output is correct
9 Correct 213 ms 31740 KB Output is correct
10 Correct 637 ms 31740 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5348 KB Output is correct
3 Correct 6 ms 5400 KB Output is correct
4 Correct 7 ms 5408 KB Output is correct
5 Correct 209 ms 19984 KB Output is correct
6 Correct 93 ms 29292 KB Output is correct
7 Correct 174 ms 29292 KB Output is correct
8 Correct 126 ms 29292 KB Output is correct
9 Correct 161 ms 29292 KB Output is correct
10 Correct 113 ms 29292 KB Output is correct
11 Correct 10 ms 31740 KB Output is correct
12 Correct 8 ms 31740 KB Output is correct
13 Correct 10 ms 31740 KB Output is correct
14 Correct 10 ms 31740 KB Output is correct
15 Correct 9 ms 31740 KB Output is correct
16 Correct 7 ms 31740 KB Output is correct
17 Correct 8 ms 31740 KB Output is correct
18 Correct 8 ms 31740 KB Output is correct
19 Correct 8 ms 31740 KB Output is correct
20 Correct 9 ms 31740 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5348 KB Output is correct
3 Correct 6 ms 5400 KB Output is correct
4 Correct 7 ms 5408 KB Output is correct
5 Correct 209 ms 19984 KB Output is correct
6 Correct 93 ms 29292 KB Output is correct
7 Correct 174 ms 29292 KB Output is correct
8 Correct 126 ms 29292 KB Output is correct
9 Correct 161 ms 29292 KB Output is correct
10 Correct 113 ms 29292 KB Output is correct
11 Correct 6 ms 29292 KB Output is correct
12 Correct 6 ms 29292 KB Output is correct
13 Correct 6 ms 29292 KB Output is correct
14 Correct 270 ms 31596 KB Output is correct
15 Correct 243 ms 31724 KB Output is correct
16 Correct 224 ms 31740 KB Output is correct
17 Correct 239 ms 31740 KB Output is correct
18 Correct 236 ms 31740 KB Output is correct
19 Correct 208 ms 31740 KB Output is correct
20 Correct 237 ms 31740 KB Output is correct
21 Correct 28 ms 31740 KB Output is correct
22 Correct 236 ms 31740 KB Output is correct
23 Correct 332 ms 31740 KB Output is correct
24 Correct 201 ms 31740 KB Output is correct
25 Correct 251 ms 31740 KB Output is correct
26 Correct 200 ms 31740 KB Output is correct
27 Correct 234 ms 31740 KB Output is correct
28 Correct 288 ms 31740 KB Output is correct
29 Correct 273 ms 31740 KB Output is correct
30 Correct 355 ms 31740 KB Output is correct
31 Correct 920 ms 31740 KB Output is correct
32 Correct 202 ms 31740 KB Output is correct
33 Correct 446 ms 31740 KB Output is correct
34 Correct 376 ms 31740 KB Output is correct
35 Correct 330 ms 31740 KB Output is correct
36 Correct 325 ms 31740 KB Output is correct
37 Correct 470 ms 31740 KB Output is correct
38 Correct 418 ms 31740 KB Output is correct
39 Correct 213 ms 31740 KB Output is correct
40 Correct 637 ms 31740 KB Output is correct
41 Correct 10 ms 31740 KB Output is correct
42 Correct 8 ms 31740 KB Output is correct
43 Correct 10 ms 31740 KB Output is correct
44 Correct 10 ms 31740 KB Output is correct
45 Correct 9 ms 31740 KB Output is correct
46 Correct 7 ms 31740 KB Output is correct
47 Correct 8 ms 31740 KB Output is correct
48 Correct 8 ms 31740 KB Output is correct
49 Correct 8 ms 31740 KB Output is correct
50 Correct 9 ms 31740 KB Output is correct
51 Correct 552 ms 31740 KB Output is correct
52 Correct 338 ms 31740 KB Output is correct
53 Correct 729 ms 31740 KB Output is correct
54 Correct 402 ms 31740 KB Output is correct
55 Execution timed out 1020 ms 31740 KB Time limit exceeded
56 Halted 0 ms 0 KB -