oj.uz

Submission #72789

# Submission time Handle Problem Language Result Execution time Memory
72789 2018-08-27T00:22:44 Z shoemakerjo Election Campaign (JOI15_election_campaign) C++14
20 / 100
 617 ms 31760 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]-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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Incorrect 617 ms 31760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -