oj.uz

Submission #114023

# Submission time Handle Problem Language Result Execution time Memory
114023 2019-05-29T15:30:42 Z Diuven Election Campaign (JOI15_election_campaign) C++14
100 / 100
 458 ms 45688 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e5+10;
const int LG = 18;

int n, de[MAX], pa[LG][MAX], su[MAX], dn[MAX];
vector<int> G[MAX];

void dfs1(int v, int p, int d=1){
	de[v] = d, su[v] = 1;
	for(int x:G[v]){
		if(x==p) continue;
		pa[0][x] = v;
		for(int i=1; i<LG; i++) pa[i][x] = pa[i-1][pa[i-1][x]];
		dfs1(x,v,d+1); su[v]+=su[x];
		if(su[dn[v]]<su[x]) dn[v]=x;
	}
}

int lca(int u, int v){
	if(de[u]<de[v]) swap(u,v);
	for(int i=LG-1; i>=0; i--) if(de[u]-(1<<i)>=de[v]) u = pa[i][u];
	if(u==v) return u;
	for(int i=LG-1; i>=0; i--) if(pa[i][u]!=pa[i][v]) u = pa[i][u], v = pa[i][v];
	return pa[0][u];
}

class Seg_t{
	int n; vector<int> T; // sum
	void upt(int v, int s, int e, int p, int x){
		if(p<s || e<p) return;
		if(s==e){ T[v]=x; return; }
		upt(v*2, s, (s+e)/2, p, x); upt(v*2+1, (s+e)/2+1, e, p, x);
		T[v] = T[v*2] + T[v*2+1];
	}
	int sum(int v, int s, int e, int l, int r){
		if(e<l || r<s) return 0;
		if(l<=s && e<=r) return T[v];
		return sum(v*2,s,(s+e)/2,l,r) + sum(v*2+1,(s+e)/2+1,e,l,r);
	}
  public:
	Seg_t(int sz): n(sz) { // [0, n)
		int k=1; while(k<sz) k<<=1;
		T.resize(k<<1, 0);
	}
    Seg_t(): Seg_t(0) {}
	void upt(int p, int x){ upt(1,0,n-1,p,x); }
	int sum(int l, int r){ return sum(1,0,n-1,l,r); }
	int val(int p){ return sum(p,p); }
};

class HLD_t{
	Seg_t Seg[MAX]; int rt[MAX], sz[MAX];
	void dfs0(int v, int p, int c){
		rt[v] = c; sz[c]++;
		for(int x:G[v]) if(x!=p)
			dfs0(x, v, (x==dn[v] ? c : x));
	}
	int sum_u(int x, int v){ // [x,v]
		int res = 0;
		for(int t, r; de[x]>=de[v]; x=pa[0][t]){
			r = rt[x], t = (de[r]<de[v] ? v : r);
			res += Seg[r].sum(de[t]-de[r], de[x]-de[r]);
		}
		return res;
	}
	int val(int v){ return Seg[rt[v]].val(de[v]-de[rt[v]]); }
  public:
    void init(){
		dfs0(1,0,1);
		for(int i=1; i<=n; i++) Seg[i] = Seg_t(sz[i]);
	}
	void upt(int v, int x){
		Seg[rt[v]].upt(de[v]-de[rt[v]], x);
	}
	int sum_p(int x, int y, int p){ return sum_u(x,p) + sum_u(y,p) - val(p); }
} HLD;

vector<int> plan[MAX];
int m, X[MAX], Y[MAX], C[MAX];

int D[MAX], S[MAX];

void dfs2(int v, int p){
	for(int x:G[v]){
		if(x==p) continue;
		dfs2(x,v); S[v]+=D[x];
	}
	D[v] = S[v]; HLD.upt(v, S[v]);

	for(int idx:plan[v]){
		int x=X[idx], y=Y[idx], c=C[idx];
		// 이걸 쓰는 경우: now = c + sum(S[x...y]) - sum(D[x...v)) - sum(D[y...v))
		// (let D[v]=0) now = c + sum(S[x...y]) - sum(D[x...y])
		int now = c + HLD.sum_p(x,y,v);
		D[v] = max(now, D[v]);
	}
	HLD.upt(v, S[v]-D[v]);
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	cin>>n;
	for(int i=1; i<n; i++){
		int u,v; cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1,0);

	HLD.init();

	cin>>m;
	for(int i=1; i<=m; i++){
		cin>>X[i]>>Y[i]>>C[i];
		plan[lca(X[i], Y[i])].push_back(i);
	}

	dfs2(1,0);

	cout<<D[1]<<'\n';

	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11392 KB Output is correct
2 Correct 15 ms 11520 KB Output is correct
3 Correct 16 ms 11520 KB Output is correct
4 Correct 15 ms 11648 KB Output is correct
5 Correct 170 ms 26252 KB Output is correct
6 Correct 99 ms 41724 KB Output is correct
7 Correct 217 ms 36216 KB Output is correct
8 Correct 153 ms 25208 KB Output is correct
9 Correct 227 ms 33304 KB Output is correct
10 Correct 155 ms 25208 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11392 KB Output is correct
2 Correct 16 ms 11392 KB Output is correct
3 Correct 16 ms 11776 KB Output is correct
4 Correct 254 ms 45432 KB Output is correct
5 Correct 240 ms 45304 KB Output is correct
6 Correct 210 ms 45304 KB Output is correct
7 Correct 236 ms 45176 KB Output is correct
8 Correct 233 ms 45304 KB Output is correct
9 Correct 211 ms 45304 KB Output is correct
10 Correct 261 ms 45248 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11392 KB Output is correct
2 Correct 16 ms 11392 KB Output is correct
3 Correct 16 ms 11776 KB Output is correct
4 Correct 254 ms 45432 KB Output is correct
5 Correct 240 ms 45304 KB Output is correct
6 Correct 210 ms 45304 KB Output is correct
7 Correct 236 ms 45176 KB Output is correct
8 Correct 233 ms 45304 KB Output is correct
9 Correct 211 ms 45304 KB Output is correct
10 Correct 261 ms 45248 KB Output is correct
11 Correct 32 ms 12488 KB Output is correct
12 Correct 276 ms 45612 KB Output is correct
13 Correct 265 ms 45560 KB Output is correct
14 Correct 226 ms 45684 KB Output is correct
15 Correct 258 ms 45584 KB Output is correct
16 Correct 238 ms 45688 KB Output is correct
17 Correct 266 ms 45560 KB Output is correct
18 Correct 266 ms 45620 KB Output is correct
19 Correct 222 ms 45560 KB Output is correct
20 Correct 264 ms 45508 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 29244 KB Output is correct
2 Correct 217 ms 45296 KB Output is correct
3 Correct 442 ms 39288 KB Output is correct
4 Correct 208 ms 28248 KB Output is correct
5 Correct 360 ms 38468 KB Output is correct
6 Correct 240 ms 28412 KB Output is correct
7 Correct 443 ms 37880 KB Output is correct
8 Correct 268 ms 29432 KB Output is correct
9 Correct 212 ms 45304 KB Output is correct
10 Correct 418 ms 36464 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11392 KB Output is correct
2 Correct 15 ms 11520 KB Output is correct
3 Correct 16 ms 11520 KB Output is correct
4 Correct 15 ms 11648 KB Output is correct
5 Correct 170 ms 26252 KB Output is correct
6 Correct 99 ms 41724 KB Output is correct
7 Correct 217 ms 36216 KB Output is correct
8 Correct 153 ms 25208 KB Output is correct
9 Correct 227 ms 33304 KB Output is correct
10 Correct 155 ms 25208 KB Output is correct
11 Correct 16 ms 11648 KB Output is correct
12 Correct 16 ms 11904 KB Output is correct
13 Correct 16 ms 11668 KB Output is correct
14 Correct 17 ms 11648 KB Output is correct
15 Correct 15 ms 11648 KB Output is correct
16 Correct 16 ms 11648 KB Output is correct
17 Correct 15 ms 11648 KB Output is correct
18 Correct 16 ms 11648 KB Output is correct
19 Correct 15 ms 11648 KB Output is correct
20 Correct 16 ms 11812 KB Output is correct

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11392 KB Output is correct
2 Correct 15 ms 11520 KB Output is correct
3 Correct 16 ms 11520 KB Output is correct
4 Correct 15 ms 11648 KB Output is correct
5 Correct 170 ms 26252 KB Output is correct
6 Correct 99 ms 41724 KB Output is correct
7 Correct 217 ms 36216 KB Output is correct
8 Correct 153 ms 25208 KB Output is correct
9 Correct 227 ms 33304 KB Output is correct
10 Correct 155 ms 25208 KB Output is correct
11 Correct 15 ms 11392 KB Output is correct
12 Correct 16 ms 11392 KB Output is correct
13 Correct 16 ms 11776 KB Output is correct
14 Correct 254 ms 45432 KB Output is correct
15 Correct 240 ms 45304 KB Output is correct
16 Correct 210 ms 45304 KB Output is correct
17 Correct 236 ms 45176 KB Output is correct
18 Correct 233 ms 45304 KB Output is correct
19 Correct 211 ms 45304 KB Output is correct
20 Correct 261 ms 45248 KB Output is correct
21 Correct 32 ms 12488 KB Output is correct
22 Correct 276 ms 45612 KB Output is correct
23 Correct 265 ms 45560 KB Output is correct
24 Correct 226 ms 45684 KB Output is correct
25 Correct 258 ms 45584 KB Output is correct
26 Correct 238 ms 45688 KB Output is correct
27 Correct 266 ms 45560 KB Output is correct
28 Correct 266 ms 45620 KB Output is correct
29 Correct 222 ms 45560 KB Output is correct
30 Correct 264 ms 45508 KB Output is correct
31 Correct 344 ms 29244 KB Output is correct
32 Correct 217 ms 45296 KB Output is correct
33 Correct 442 ms 39288 KB Output is correct
34 Correct 208 ms 28248 KB Output is correct
35 Correct 360 ms 38468 KB Output is correct
36 Correct 240 ms 28412 KB Output is correct
37 Correct 443 ms 37880 KB Output is correct
38 Correct 268 ms 29432 KB Output is correct
39 Correct 212 ms 45304 KB Output is correct
40 Correct 418 ms 36464 KB Output is correct
41 Correct 16 ms 11648 KB Output is correct
42 Correct 16 ms 11904 KB Output is correct
43 Correct 16 ms 11668 KB Output is correct
44 Correct 17 ms 11648 KB Output is correct
45 Correct 15 ms 11648 KB Output is correct
46 Correct 16 ms 11648 KB Output is correct
47 Correct 15 ms 11648 KB Output is correct
48 Correct 16 ms 11648 KB Output is correct
49 Correct 15 ms 11648 KB Output is correct
50 Correct 16 ms 11812 KB Output is correct
51 Correct 309 ms 29652 KB Output is correct
52 Correct 259 ms 45616 KB Output is correct
53 Correct 439 ms 36744 KB Output is correct
54 Correct 235 ms 28540 KB Output is correct
55 Correct 354 ms 29428 KB Output is correct
56 Correct 253 ms 45564 KB Output is correct
57 Correct 384 ms 37880 KB Output is correct
58 Correct 228 ms 28404 KB Output is correct
59 Correct 317 ms 29660 KB Output is correct
60 Correct 293 ms 45688 KB Output is correct
61 Correct 357 ms 38136 KB Output is correct
62 Correct 219 ms 28464 KB Output is correct
63 Correct 338 ms 29616 KB Output is correct
64 Correct 270 ms 45532 KB Output is correct
65 Correct 458 ms 37876 KB Output is correct
66 Correct 238 ms 28580 KB Output is correct
67 Correct 346 ms 29760 KB Output is correct
68 Correct 279 ms 45680 KB Output is correct
69 Correct 419 ms 35776 KB Output is correct
70 Correct 246 ms 28496 KB Output is correct