Submission #154280

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
154280	2019-09-20T07:52:19 Z	ryansee	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	752 ms	112608 KB

election_campaign

#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb emplace_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos(-1))
#define MAXN (300006)
#define MAXK 26
#define MAXX 15000006
#define ll long long int 
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph emplace
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n,m;
vector<int>v[MAXN];
struct lca_{
	int st[MAXN], en[MAXN], co, p[MAXN][21], depth[MAXN];
	lca_() {
		mmst(st,0); mmst(en,0); co =0 ; mmst(p,0); mmst(depth,0);
	}
	void dfs(ll x, ll par) {
		p[x][0] = par;
		st[x]=co++;
		for(auto i : v[x]) if(i!=par) {
			depth[i]=depth[x]+1;dfs(i,x);
		}
		en[x]=co;
	}
	void main() {
		co=0;
		dfs(1,1);
		t2k();
	}
	void t2k() { for(ll j=1;j<21;j++) for(ll i=1;i<=n;i++) p[i][j]=p[p[i][j-1]][j-1]; }
	ll lca(ll x, ll y) {
		if(isp(x,y)) return x;
		if(isp(y,x)) return y;
		for(ll i=20;i>=0;i--) {
			if(!isp(p[x][i],y)) x=p[x][i];
		}
		return p[x][0];
	}
	bool isp(ll a, ll b) { return st[a]<=st[b]&&en[a]>=en[b]; }
	ll find2k(ll x, ll k) {
		for(ll i=20;i>=0;i--) {
			if(k>=(1ll<<i)) {
				k -= (1ll<<i);
				x=p[x][i];
			}
		}
		assert(k==0);
		return x;
	}
} lca;
spi Q[MAXN];
vector<pair<ll,bool>>at[MAXN];
set<ll>*s[MAXN];
ll dp[MAXN],sumy[MAXN];
struct fen {
	ll fw[MAXN]={0};
	fen() {mmst(fw,0); }
	void update(ll x, ll nv) { for(; x<=n;x+=x&(-x)) fw[x]+=nv;}
	ll sum(ll x) {ll res=0;for(;x;x-=x&(-x)) res+=fw[x];return res;}
	ll sum(ll a,ll b){return sum(b)-sum(a-1);} 
}fen;
struct hld_ {
	int st[MAXN],p[MAXN],depth[MAXN],head[MAXN],heavy[MAXN],co=0;
	hld_(){ FOR(i,0,MAXN)st[i]=p[i]=depth[i]=head[i]=0,heavy[i]=-1; }
	ll dfs(ll x, ll p){
		ll sz=1;
		ll mx_sz=0; 
		for(auto i:v[x])if(i!=p){
			depth[i]=depth[x]+1;
			ll c_sz=dfs(i,x);
			sz+=c_sz;
			if(c_sz>mx_sz){mx_sz=c_sz;heavy[x]=i;}
		}
		return sz;
	}
	void main(){
		dfs(1,1);
		co=1;hld(1,1,1);
		return;
	}
	void hld(ll x, ll h, ll par){
		p[x]=par;
		head[x]=h;
		st[x]=co++;
		if(heavy[x]!=-1)
			hld(heavy[x],h,x);
		for(auto i:v[x])if(i!=par&&i!=heavy[x]){
			hld(i,i,x);
		}
		return;
	}
	ll query(ll a, ll b){
		ll ans=0;
		for(;head[a]!=head[b];a=p[head[a]]){
			if(depth[head[a]]<depth[head[b]])swap(a,b);
			ans+=fen.sum(st[head[a]],st[a]);
		}
		if(depth[a]>depth[b])swap(a,b);
		return ans+fen.sum(st[a],st[b]);
	}
	void update(ll x, ll nv) { assert(1<=st[x]&&st[x]<=n); fen.update(st[x], nv); }
} hld;
void up(ll &x, ll y) { x=max(x,y); }
void dfs(ll x, ll p) {
	ll sum = 0;
	for(auto i : v[x]) if(i!=p) {
		dfs(i,x); sum+=dp[i];
	}
	sumy[x]=dp[x]=sum;
	s[x] = new set<ll>; ll poi=-1;
	for(auto i:v[x])if(i!=p){
		if(s[i]->size()>s[x]->size())s[x]=s[i],poi=i;
	}
	for(auto i:v[x])if(i!=p&&i!=poi){
		for(auto j:*s[i])s[x]->ins(j);
	}
	/* handle answer part */
	for(auto i:at[x]) {
		if(i.s) {
			ll ind = i.f;
			assert(s[x]->count(ind));
			ll a=Q[ind].s.f,b=Q[ind].s.s,c=Q[ind].f;
			if(a==x||b==x) {
				if(b==x) swap(a,b);
				ll be = lca.find2k(b,lca.depth[b]-lca.depth[x]-1);
				assert(~be);
				// dp[x] = max(dp[x], sum+c+sumy[b]-dp[be]);
				ll val = ((hld.depth[be] <= hld.depth[hld.p[b]]) ? hld.query(hld.p[b],be)+sum-dp[b]+sumy[b] : sum-dp[be]+sumy[b])+c;
				up(dp[x],val);
			} else { // assert(0);
				ll bea=-1,beb=-1; bea = lca.find2k(a, lca.depth[a]-lca.depth[x]-1); beb = lca.find2k(b, lca.depth[b]-lca.depth[x]-1);
				// for(auto i:v[x])if(i!=p){if(lca.isp(i,a))bea=i;}
				// for(auto i:v[x])if(i!=p){if(lca.isp(i,b))beb=i;}
				assert((~bea)&&(~beb));
				// cerr << "Query: " << x << ' ' << a << ' ' << bea << ' ' << b << ' ' << beb << ' ';
				// dp[x]=max(dp[x],sum+c+sumy[a]+sumy[b]-dp[bea]-dp[beb]);
				ll val = 0;
				ll separate = sum - dp[bea] - dp[beb];
				ll b_side = ((hld.depth[beb] <= hld.depth[hld.p[b]]) ? (hld.query(beb, hld.p[b])-separate-dp[bea]-dp[b]+sum+sumy[b]) : sumy[b]);
				ll a_side = ((hld.depth[bea] <= hld.depth[hld.p[a]]) ? (hld.query(bea, hld.p[a])-separate-dp[beb]-dp[a]+sum+sumy[a]) : sumy[a]);
				// cerr<<b_side<<' '<<a_side<<'\n';
				val = separate + a_side + b_side + c;
				up(dp[x],val);
			}
			s[x]->erase(ind);
		} else {
			s[x]->ins(i.f);
		}
	}
	/* */
	assert(dp[x]>=sumy[x]);
	hld.update(x,sumy[x]-dp[x]);
		// cerr<<x<<": "<<dp[x]<<'\n';
}
bool openfile=0;
int main()
{ if(openfile)freopen("int","r",stdin);
	FAST
	cin>>n;
	FOR(i,1,n) { ll a,b;cin>>a>>b;v[a].pb(b);v[b].pb(a); }
	cin>>m;
	FOR(i,0,m) {
		cin>>Q[i].s.f>>Q[i].s.s>>Q[i].f;
	}
	lca.main(); hld.main();
	// 0-start, 1-end
	FOR(i,0,m) {
		ll a,b;tie(a,b)=Q[i].s;
		ll la=lca.lca(a,b);
		if(a!=la)at[a].pb(i,0);
		if(b!=la)at[b].pb(i,0);
		at[la].pb(i,1);
	}
	dfs(1,1);	
	cout<<dp[1]<<'\n';
}

/*
 * 
7
1 2
2 3
3 4
2 5
4 6
3 7
2
5 1 7
6 3 10

*/

Compilation message

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:181:22: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 { if(openfile)freopen("int","r",stdin);
               ~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	50780 KB	Output is correct
2	Correct	47 ms	50808 KB	Output is correct
3	Correct	56 ms	50808 KB	Output is correct
4	Correct	47 ms	51064 KB	Output is correct
5	Correct	218 ms	63956 KB	Output is correct
6	Correct	130 ms	82652 KB	Output is correct
7	Correct	188 ms	76080 KB	Output is correct
8	Correct	204 ms	64360 KB	Output is correct
9	Correct	238 ms	72372 KB	Output is correct
10	Correct	174 ms	64248 KB	Output is correct

Subtask #2

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	50936 KB	Output is correct
2	Correct	46 ms	50784 KB	Output is correct
3	Correct	48 ms	51192 KB	Output is correct
4	Correct	424 ms	92708 KB	Output is correct
5	Correct	421 ms	92740 KB	Output is correct
6	Correct	312 ms	91448 KB	Output is correct
7	Correct	436 ms	92920 KB	Output is correct
8	Correct	367 ms	92848 KB	Output is correct
9	Correct	299 ms	91520 KB	Output is correct
10	Correct	354 ms	92732 KB	Output is correct

Subtask #3

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	50936 KB	Output is correct
2	Correct	46 ms	50784 KB	Output is correct
3	Correct	48 ms	51192 KB	Output is correct
4	Correct	424 ms	92708 KB	Output is correct
5	Correct	421 ms	92740 KB	Output is correct
6	Correct	312 ms	91448 KB	Output is correct
7	Correct	436 ms	92920 KB	Output is correct
8	Correct	367 ms	92848 KB	Output is correct
9	Correct	299 ms	91520 KB	Output is correct
10	Correct	354 ms	92732 KB	Output is correct
11	Correct	75 ms	53496 KB	Output is correct
12	Correct	362 ms	93068 KB	Output is correct
13	Correct	373 ms	93036 KB	Output is correct
14	Correct	307 ms	91764 KB	Output is correct
15	Correct	372 ms	93124 KB	Output is correct
16	Correct	294 ms	91640 KB	Output is correct
17	Correct	367 ms	93204 KB	Output is correct
18	Correct	363 ms	93176 KB	Output is correct
19	Correct	294 ms	91840 KB	Output is correct
20	Correct	359 ms	93064 KB	Output is correct

Subtask #4

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	678 ms	111608 KB	Output is correct
2	Correct	287 ms	91384 KB	Output is correct
3	Correct	579 ms	90152 KB	Output is correct
4	Correct	433 ms	89900 KB	Output is correct
5	Correct	452 ms	85900 KB	Output is correct
6	Correct	500 ms	88068 KB	Output is correct
7	Correct	616 ms	89876 KB	Output is correct
8	Correct	445 ms	86236 KB	Output is correct
9	Correct	294 ms	91556 KB	Output is correct
10	Correct	551 ms	88936 KB	Output is correct

Subtask #5

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	50780 KB	Output is correct
2	Correct	47 ms	50808 KB	Output is correct
3	Correct	56 ms	50808 KB	Output is correct
4	Correct	47 ms	51064 KB	Output is correct
5	Correct	218 ms	63956 KB	Output is correct
6	Correct	130 ms	82652 KB	Output is correct
7	Correct	188 ms	76080 KB	Output is correct
8	Correct	204 ms	64360 KB	Output is correct
9	Correct	238 ms	72372 KB	Output is correct
10	Correct	174 ms	64248 KB	Output is correct
11	Correct	49 ms	51448 KB	Output is correct
12	Correct	56 ms	51320 KB	Output is correct
13	Correct	55 ms	51164 KB	Output is correct
14	Correct	58 ms	51164 KB	Output is correct
15	Correct	58 ms	51320 KB	Output is correct
16	Correct	55 ms	51192 KB	Output is correct
17	Correct	49 ms	51320 KB	Output is correct
18	Correct	49 ms	51320 KB	Output is correct
19	Correct	48 ms	51212 KB	Output is correct
20	Correct	47 ms	51320 KB	Output is correct

Subtask #6

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	50780 KB	Output is correct
2	Correct	47 ms	50808 KB	Output is correct
3	Correct	56 ms	50808 KB	Output is correct
4	Correct	47 ms	51064 KB	Output is correct
5	Correct	218 ms	63956 KB	Output is correct
6	Correct	130 ms	82652 KB	Output is correct
7	Correct	188 ms	76080 KB	Output is correct
8	Correct	204 ms	64360 KB	Output is correct
9	Correct	238 ms	72372 KB	Output is correct
10	Correct	174 ms	64248 KB	Output is correct
11	Correct	46 ms	50936 KB	Output is correct
12	Correct	46 ms	50784 KB	Output is correct
13	Correct	48 ms	51192 KB	Output is correct
14	Correct	424 ms	92708 KB	Output is correct
15	Correct	421 ms	92740 KB	Output is correct
16	Correct	312 ms	91448 KB	Output is correct
17	Correct	436 ms	92920 KB	Output is correct
18	Correct	367 ms	92848 KB	Output is correct
19	Correct	299 ms	91520 KB	Output is correct
20	Correct	354 ms	92732 KB	Output is correct
21	Correct	75 ms	53496 KB	Output is correct
22	Correct	362 ms	93068 KB	Output is correct
23	Correct	373 ms	93036 KB	Output is correct
24	Correct	307 ms	91764 KB	Output is correct
25	Correct	372 ms	93124 KB	Output is correct
26	Correct	294 ms	91640 KB	Output is correct
27	Correct	367 ms	93204 KB	Output is correct
28	Correct	363 ms	93176 KB	Output is correct
29	Correct	294 ms	91840 KB	Output is correct
30	Correct	359 ms	93064 KB	Output is correct
31	Correct	678 ms	111608 KB	Output is correct
32	Correct	287 ms	91384 KB	Output is correct
33	Correct	579 ms	90152 KB	Output is correct
34	Correct	433 ms	89900 KB	Output is correct
35	Correct	452 ms	85900 KB	Output is correct
36	Correct	500 ms	88068 KB	Output is correct
37	Correct	616 ms	89876 KB	Output is correct
38	Correct	445 ms	86236 KB	Output is correct
39	Correct	294 ms	91556 KB	Output is correct
40	Correct	551 ms	88936 KB	Output is correct
41	Correct	49 ms	51448 KB	Output is correct
42	Correct	56 ms	51320 KB	Output is correct
43	Correct	55 ms	51164 KB	Output is correct
44	Correct	58 ms	51164 KB	Output is correct
45	Correct	58 ms	51320 KB	Output is correct
46	Correct	55 ms	51192 KB	Output is correct
47	Correct	49 ms	51320 KB	Output is correct
48	Correct	49 ms	51320 KB	Output is correct
49	Correct	48 ms	51212 KB	Output is correct
50	Correct	47 ms	51320 KB	Output is correct
51	Correct	422 ms	86368 KB	Output is correct
52	Correct	361 ms	93048 KB	Output is correct
53	Correct	598 ms	89532 KB	Output is correct
54	Correct	378 ms	82808 KB	Output is correct
55	Correct	609 ms	111308 KB	Output is correct
56	Correct	363 ms	92980 KB	Output is correct
57	Correct	470 ms	85372 KB	Output is correct
58	Correct	557 ms	90080 KB	Output is correct
59	Correct	674 ms	86436 KB	Output is correct
60	Correct	438 ms	93072 KB	Output is correct
61	Correct	491 ms	85492 KB	Output is correct
62	Correct	458 ms	90756 KB	Output is correct
63	Correct	613 ms	111972 KB	Output is correct
64	Correct	422 ms	93156 KB	Output is correct
65	Correct	586 ms	89768 KB	Output is correct
66	Correct	417 ms	81432 KB	Output is correct
67	Correct	752 ms	112608 KB	Output is correct
68	Correct	444 ms	93108 KB	Output is correct
69	Correct	450 ms	82932 KB	Output is correct
70	Correct	548 ms	86752 KB	Output is correct