oj.uz

Submission #36101

# Submission time Handle Problem Language Result Execution time Memory
36101 2017-12-05T14:51:53 Z UncleGrandpa925 Election Campaign (JOI15_election_campaign) C++14
100 / 100
 756 ms 78248 KB 
/*input
7
3 4
6 5
2 7
1 5
7 5
4 5
5
4 3 10
5 6 5
2 6 9
7 2 2
1 3 8
*/
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define int long long
#define N 100005
#define bit(x,y) ((x>>y)&1LL)
#define na(x) (#x) << ":" << x
ostream& operator << (ostream &os, vector<int>&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << sp;
	return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
	cout << x.fi << sp << x.se << sp;
	return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << endl;
	return os;
}
struct data {
	int u, v, w;
	data(int _u, int _v, int _w): u(_u), v(_v), w(_w) {};
};

int n, m;
vector<vector<int> > a(N);
vector<vector<int> > b(N);
vector<vector<data> > go(N);

int par[N][22];
int dis[N];
int sta[N], en[N], Time = 0;

void dfs(int u, int p) {
	par[u][0] = p; sta[u] = ++Time;
	for (int i = 0; i < a[u].size(); i++) {
		int v = a[u][i];
		if (v != p) {
			b[u].push_back(v);
			dis[v] = dis[u] + 1;
			dfs(v, u);
		}
	}
	en[u] = Time;
}

int lca(int p, int q) {
	if (dis[p] < dis[q]) swap(p, q);
	for (int i = 20; i >= 0; i--) {
		if (dis[par[p][i]] >= dis[q]) {
			p = par[p][i];
		}
	}
	if (p == q) return p;
	for (int i = 20; i >= 0; i--) {
		if (par[p][i] != par[q][i]) {
			p = par[p][i];
			q = par[q][i];
		}
	}
	return par[p][0];
}

void makelca() {
	dfs(1, 1);
	for (int i = 1; i <= 20; i++) {
		for (int j = 1; j <= n; j++) {
			par[j][i] = par[par[j][i - 1]][i - 1];
		}
	}
}

class ITrangeSum {
private:
	int f[4 * N];
	int lazy[4 * N];
	void dolazy(int k, int l, int r) {
		if (lazy[k] == 0) return;
		f[k] += lazy[k] * (r - l + 1);
		if (l != r) {
			lazy[k * 2] += lazy[k];
			lazy[k * 2 + 1] += lazy[k];
		}
		lazy[k] = 0;
	}
public:
	void update(int k, int l, int r, int L, int R, int val) {
		dolazy(k, l, r);
		if (r < L || R < l) return;
		if (L <= l && r <= R) {
			f[k] += val * (r - l + 1);
			if (l != r) {
				lazy[k * 2] += val;
				lazy[k * 2 + 1] += val;
			}
			return;
		}
		int mid = (l + r) / 2;
		update(k * 2, l, mid, L, R, val); update(k * 2 + 1, mid + 1, r, L, R, val);
		f[k] = f[k * 2] + f[k * 2 + 1];
	}
	int get(int k, int l, int r, int L, int R) {
		dolazy(k, l, r);
		if (r < L || R < l) return 0;
		if (L <= l && r <= R) return f[k];
		int mid = (l + r) / 2;
		return get(k * 2, l, mid, L, R) + get(k * 2 + 1, mid + 1, r, L, R);
	}
} IT;

int getDescendant(int u, int v) {
	int l = 0, r = a[u].size() - 1;
	while (l != r) {
		int mid = (l + r + 1) / 2;
		if (sta[a[u][mid]] <= sta[v]) l = mid;
		else r = mid - 1;
	}
	return a[u][l];
}

int dp[N];
void solve(int u) {
	int sum = 0;
	for (auto v : a[u]) {
		solve(v);
		sum += dp[v];
	}
	dp[u] = sum;
	for (int i = 0; i < go[u].size(); i++) {
		int fl = go[u][i].u; int fr = go[u][i].v; int w = go[u][i].w;
		if (fl == u) dp[u] = max(dp[u], sum - dp[getDescendant(u, fr)] + IT.get(1, 1, n, sta[fr], sta[fr]) + w);
		else if (fr == u) dp[u] = max(dp[u], sum - dp[getDescendant(u, fl)] + IT.get(1, 1, n, sta[fl], sta[fl]) + w);
		else dp[u] = max(dp[u], sum - dp[getDescendant(u, fr)] - dp[getDescendant(u, fl)] + IT.get(1, 1, n, sta[fl], sta[fl]) + IT.get(1, 1, n, sta[fr], sta[fr]) + w);
	}
	for (auto v : a[u]) 
		IT.update(1, 1, n, sta[v], en[v], sum - dp[v]);
	IT.update(1, 1, n, sta[u], sta[u], sum);
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n - 1; i++) {
		int u, v; cin >> u >> v;
		a[u].push_back(v); a[v].push_back(u);
	}
	makelca();
	cin >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		go[lca(u, v)].push_back(data(u, v, w));
	}
	a.swap(b);
	solve(1);
	cout << dp[1] << endl;
}

Compilation message

election_campaign.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<long long int>&)':
election_campaign.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << sp;
                    ^
election_campaign.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<long long int, long long int> >&)':
election_campaign.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                    ^
election_campaign.cpp: In function 'void dfs(long long int, long long int)':
election_campaign.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a[u].size(); i++) {
                    ^
election_campaign.cpp: In function 'void solve(long long int)':
election_campaign.cpp:148:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < go[u].size(); i++) {
                    ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 35788 KB Output is correct
2 Correct 0 ms 35788 KB Output is correct
3 Correct 0 ms 35788 KB Output is correct
4 Correct 0 ms 35788 KB Output is correct
5 Correct 256 ms 41332 KB Output is correct
6 Correct 139 ms 74676 KB Output is correct
7 Correct 249 ms 62948 KB Output is correct
8 Correct 199 ms 41576 KB Output is correct
9 Correct 286 ms 56440 KB Output is correct
10 Correct 196 ms 41572 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 35788 KB Output is correct
2 Correct 6 ms 35788 KB Output is correct
3 Correct 3 ms 35992 KB Output is correct
4 Correct 409 ms 78244 KB Output is correct
5 Correct 389 ms 78244 KB Output is correct
6 Correct 326 ms 78244 KB Output is correct
7 Correct 386 ms 78248 KB Output is correct
8 Correct 453 ms 78240 KB Output is correct
9 Correct 366 ms 78248 KB Output is correct
10 Correct 423 ms 78244 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 35788 KB Output is correct
2 Correct 6 ms 35788 KB Output is correct
3 Correct 3 ms 35992 KB Output is correct
4 Correct 409 ms 78244 KB Output is correct
5 Correct 389 ms 78244 KB Output is correct
6 Correct 326 ms 78244 KB Output is correct
7 Correct 386 ms 78248 KB Output is correct
8 Correct 453 ms 78240 KB Output is correct
9 Correct 366 ms 78248 KB Output is correct
10 Correct 423 ms 78244 KB Output is correct
11 Correct 26 ms 36912 KB Output is correct
12 Correct 426 ms 78240 KB Output is correct
13 Correct 419 ms 78244 KB Output is correct
14 Correct 326 ms 78244 KB Output is correct
15 Correct 396 ms 78248 KB Output is correct
16 Correct 363 ms 78244 KB Output is correct
17 Correct 399 ms 78244 KB Output is correct
18 Correct 456 ms 78244 KB Output is correct
19 Correct 339 ms 78244 KB Output is correct
20 Correct 396 ms 78240 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 44724 KB Output is correct
2 Correct 376 ms 78240 KB Output is correct
3 Correct 716 ms 65520 KB Output is correct
4 Correct 443 ms 45484 KB Output is correct
5 Correct 643 ms 63052 KB Output is correct
6 Correct 439 ms 45944 KB Output is correct
7 Correct 666 ms 62532 KB Output is correct
8 Correct 533 ms 44676 KB Output is correct
9 Correct 299 ms 78244 KB Output is correct
10 Correct 679 ms 59024 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 35788 KB Output is correct
2 Correct 0 ms 35788 KB Output is correct
3 Correct 0 ms 35788 KB Output is correct
4 Correct 0 ms 35788 KB Output is correct
5 Correct 256 ms 41332 KB Output is correct
6 Correct 139 ms 74676 KB Output is correct
7 Correct 249 ms 62948 KB Output is correct
8 Correct 199 ms 41576 KB Output is correct
9 Correct 286 ms 56440 KB Output is correct
10 Correct 196 ms 41572 KB Output is correct
11 Correct 0 ms 35788 KB Output is correct
12 Correct 0 ms 35992 KB Output is correct
13 Correct 0 ms 35876 KB Output is correct
14 Correct 0 ms 35924 KB Output is correct
15 Correct 3 ms 35920 KB Output is correct
16 Correct 0 ms 35788 KB Output is correct
17 Correct 0 ms 35788 KB Output is correct
18 Correct 0 ms 35880 KB Output is correct
19 Correct 6 ms 35924 KB Output is correct
20 Correct 6 ms 35996 KB Output is correct

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 35788 KB Output is correct
2 Correct 0 ms 35788 KB Output is correct
3 Correct 0 ms 35788 KB Output is correct
4 Correct 0 ms 35788 KB Output is correct
5 Correct 256 ms 41332 KB Output is correct
6 Correct 139 ms 74676 KB Output is correct
7 Correct 249 ms 62948 KB Output is correct
8 Correct 199 ms 41576 KB Output is correct
9 Correct 286 ms 56440 KB Output is correct
10 Correct 196 ms 41572 KB Output is correct
11 Correct 0 ms 35788 KB Output is correct
12 Correct 6 ms 35788 KB Output is correct
13 Correct 3 ms 35992 KB Output is correct
14 Correct 409 ms 78244 KB Output is correct
15 Correct 389 ms 78244 KB Output is correct
16 Correct 326 ms 78244 KB Output is correct
17 Correct 386 ms 78248 KB Output is correct
18 Correct 453 ms 78240 KB Output is correct
19 Correct 366 ms 78248 KB Output is correct
20 Correct 423 ms 78244 KB Output is correct
21 Correct 26 ms 36912 KB Output is correct
22 Correct 426 ms 78240 KB Output is correct
23 Correct 419 ms 78244 KB Output is correct
24 Correct 326 ms 78244 KB Output is correct
25 Correct 396 ms 78248 KB Output is correct
26 Correct 363 ms 78244 KB Output is correct
27 Correct 399 ms 78244 KB Output is correct
28 Correct 456 ms 78244 KB Output is correct
29 Correct 339 ms 78244 KB Output is correct
30 Correct 396 ms 78240 KB Output is correct
31 Correct 493 ms 44724 KB Output is correct
32 Correct 376 ms 78240 KB Output is correct
33 Correct 716 ms 65520 KB Output is correct
34 Correct 443 ms 45484 KB Output is correct
35 Correct 643 ms 63052 KB Output is correct
36 Correct 439 ms 45944 KB Output is correct
37 Correct 666 ms 62532 KB Output is correct
38 Correct 533 ms 44676 KB Output is correct
39 Correct 299 ms 78244 KB Output is correct
40 Correct 679 ms 59024 KB Output is correct
41 Correct 0 ms 35788 KB Output is correct
42 Correct 0 ms 35992 KB Output is correct
43 Correct 0 ms 35876 KB Output is correct
44 Correct 0 ms 35924 KB Output is correct
45 Correct 3 ms 35920 KB Output is correct
46 Correct 0 ms 35788 KB Output is correct
47 Correct 0 ms 35788 KB Output is correct
48 Correct 0 ms 35880 KB Output is correct
49 Correct 6 ms 35924 KB Output is correct
50 Correct 6 ms 35996 KB Output is correct
51 Correct 443 ms 44712 KB Output is correct
52 Correct 383 ms 78244 KB Output is correct
53 Correct 643 ms 59516 KB Output is correct
54 Correct 396 ms 44976 KB Output is correct
55 Correct 513 ms 45256 KB Output is correct
56 Correct 356 ms 78244 KB Output is correct
57 Correct 563 ms 61152 KB Output is correct
58 Correct 433 ms 45032 KB Output is correct
59 Correct 499 ms 44752 KB Output is correct
60 Correct 383 ms 78248 KB Output is correct
61 Correct 569 ms 61580 KB Output is correct
62 Correct 396 ms 46260 KB Output is correct
63 Correct 483 ms 45424 KB Output is correct
64 Correct 463 ms 78244 KB Output is correct
65 Correct 756 ms 62128 KB Output is correct
66 Correct 389 ms 45072 KB Output is correct
67 Correct 473 ms 46164 KB Output is correct
68 Correct 349 ms 78244 KB Output is correct
69 Correct 503 ms 56248 KB Output is correct
70 Correct 423 ms 45604 KB Output is correct