oj.uz

Submission #235883

# Submission time Handle Problem Language Result Execution time Memory
235883 2020-05-30T10:09:47 Z kshitij_sodani Election Campaign (JOI15_election_campaign) C++17
10 / 100
 289 ms 49684 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
llo n,m;
llo ac,bc,dd;
llo par[100001][20];
llo lev[100001];
vector<llo> adj[100001];
llo co=0;
llo st[100001];
llo en[100001];
llo dp[100001];
llo tree[400001];
llo lazy[400001];
vector<pair<pair<llo,llo>,pair<llo,llo>>> pre[100001];
vector<llo> pre2[100001];
void update(llo no,llo l,llo r,llo aa,llo bb,llo val){
	if(lazy[no]!=0){
		tree[no]+=lazy[no];
		if(l<r){
			lazy[no*2+1]+=lazy[no];
			lazy[no*2+2]+=lazy[no];
		}
		lazy[no]=0;
	}
	if(r<aa or l>bb){
		return;
	}
	if(aa<=l and r<=bb){
		tree[no]+=val;
		if(l<r){
			tree[no*2+1]+=val;
			tree[no*2+2]+=val;
		}
	}
	else{
		llo mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,val);
		update(no*2+2,mid+1,r,aa,bb,val);
		tree[no]=tree[no*2+1]+tree[no*2+2];
	}
}
llo query(llo no,llo l,llo r,llo i){
	if(lazy[no]!=0){
		tree[no]+=lazy[no];
		if(l<r){
			lazy[no*2+1]+=lazy[no];
			lazy[no*2+2]+=lazy[no];
		}
		lazy[no]=0;
	}
	if(l==r){
		return tree[no];
	}
	llo mid=(l+r)/2;
	if(i<=mid){
		return query(no*2+1,l,mid,i);
	}
	else{
		return query(no*2+2,mid+1,r,i);
	}
}
llo dfs(llo no,llo par2=-1,llo levv=0){
	st[no]=co;
	co+=1;
	par[no][0]=par2;
	lev[no]=levv;
	for(auto j:adj[no]){
		if(j==par2){
			continue;
		}
		dfs(j,no,levv+1);
	}
	en[no]=co-1;
}
llo kk(llo aa,llo k){
	for(llo j=19;j>=0;j--){
		if((1<<j)&k){
			aa=par[aa][j];
		}
	}
	return aa;
}
pair<llo,pair<llo,llo>> lca(llo aa,llo bb){
	llo cc,dd;
	cc=aa;
	dd=bb;
	if(lev[aa]>lev[bb]){
		aa=kk(aa,abs(lev[bb]-lev[aa]));
		if(aa==bb){
			return {aa,{kk(cc,abs(lev[bb]-lev[cc])-1),-1}};
		}
	}
	else{
		bb=kk(bb,abs(lev[bb]-lev[aa]));
		if(aa==bb){
			return {aa,{-1,kk(dd,abs(lev[bb]-lev[dd])-1)}};
		}
	}
	for(llo j=19;j>=0;j--){
		if(par[aa][j]!=par[bb][j]){
			aa=par[aa][j];
			bb=par[bb][j];
		}
	}
	return {par[aa][0],{kk(cc,abs(lev[cc]-lev[par[aa][0]])-1),kk(dd,abs(lev[dd]-lev[par[aa][0]])-1)}};
}
llo dfs2(llo no,llo par2=-1){
	llo su=0;
	for(auto j:adj[no]){
		if(j!=par2){
			dfs2(j,no);
			su+=dp[j];
		}
	}
	dp[no]=su;
	for(llo j=0;j<pre[no].size();j++){
		pair<pair<llo,llo>,pair<llo,llo>> kk=pre[no][j];
		llo cost=pre2[no][j];
		if(kk.b.a==-1){
			cost+=su;
			cost-=dp[kk.b.b];
			cost+=query(0,0,n-1,st[kk.a.b]);

		}
		else if(kk.b.b==-1){
			cost+=su;
			cost-=dp[kk.b.a];
			cost+=query(0,0,n-1,st[kk.a.a]);
		}
		else{
			cost+=su;
			cost-=dp[kk.b.b];
			cost-=dp[kk.b.a];
			cost+=query(0,0,n-1,st[kk.a.b]);
			cost+=query(0,0,n-1,st[kk.a.a]);
		}
		dp[no]=max(dp[no],cost);
	}
	update(0,0,n-1,st[no],st[no],su);
	for(auto j:adj[no]){
		if(j==par2){
			continue;
		}
		update(0,0,n-1,st[j],en[j],su-dp[j]);
	}
}

int main(){
	memset(tree,0,sizeof(tree));
	memset(lazy,0,sizeof(lazy));
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n-1;i++){
		cin>>ac>>bc;
		adj[ac-1].pb(bc-1);
		adj[bc-1].pb(ac-1);
	}
	dfs(0);
	cin>>m;
	for(llo j=1;j<20;j++){
		for(llo i=0;i<n;i++){
			if(par[i][j-1]==-1){
				par[i][j]=-1;
			}
			else{
				par[i][j]=par[par[i][j-1]][j-1];
			}
		}
	}
	for(llo i=0;i<m;i++){
		cin>>ac>>bc>>dd;
		pair<llo,pair<llo,llo>> cc=lca(ac-1,bc-1);
		pre[cc.a].pb({{ac-1,bc-1},{cc.b}});
		pre2[cc.a].pb(dd);
		if(cc.a==-1){
			while(true){
				continue;
			}
		}
	//	cout<<cc.a<<","<<cc.b.a<<","<<cc.b.b<<endl;
	}
	dfs2(0);
	cout<<dp[0]<<endl;


	
	return 0;
}

Compilation message

election_campaign.cpp: In function 'llo dfs(llo, llo, llo)':
election_campaign.cpp:79:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
election_campaign.cpp: In function 'llo dfs2(llo, llo)':
election_campaign.cpp:121:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(llo j=0;j<pre[no].size();j++){
              ~^~~~~~~~~~~~~~~
election_campaign.cpp:151:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 13696 KB Output is correct
2 Correct 12 ms 13696 KB Output is correct
3 Correct 13 ms 13696 KB Output is correct
4 Correct 13 ms 13952 KB Output is correct
5 Incorrect 168 ms 36344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 13696 KB Output is correct
2 Correct 13 ms 13696 KB Output is correct
3 Correct 13 ms 13952 KB Output is correct
4 Correct 246 ms 49560 KB Output is correct
5 Correct 250 ms 49528 KB Output is correct
6 Correct 231 ms 49528 KB Output is correct
7 Correct 252 ms 49528 KB Output is correct
8 Correct 248 ms 49528 KB Output is correct
9 Correct 222 ms 49656 KB Output is correct
10 Correct 260 ms 49528 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 13696 KB Output is correct
2 Correct 13 ms 13696 KB Output is correct
3 Correct 13 ms 13952 KB Output is correct
4 Correct 246 ms 49560 KB Output is correct
5 Correct 250 ms 49528 KB Output is correct
6 Correct 231 ms 49528 KB Output is correct
7 Correct 252 ms 49528 KB Output is correct
8 Correct 248 ms 49528 KB Output is correct
9 Correct 222 ms 49656 KB Output is correct
10 Correct 260 ms 49528 KB Output is correct
11 Correct 26 ms 15360 KB Output is correct
12 Correct 274 ms 49572 KB Output is correct
13 Correct 242 ms 49528 KB Output is correct
14 Correct 239 ms 49656 KB Output is correct
15 Correct 263 ms 49556 KB Output is correct
16 Correct 230 ms 49528 KB Output is correct
17 Correct 262 ms 49656 KB Output is correct
18 Correct 278 ms 49684 KB Output is correct
19 Correct 237 ms 49528 KB Output is correct
20 Correct 269 ms 49528 KB Output is correct

Subtask #4
0 / 30.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 13696 KB Output is correct
2 Correct 12 ms 13696 KB Output is correct
3 Correct 13 ms 13696 KB Output is correct
4 Correct 13 ms 13952 KB Output is correct
5 Incorrect 168 ms 36344 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 13696 KB Output is correct
2 Correct 12 ms 13696 KB Output is correct
3 Correct 13 ms 13696 KB Output is correct
4 Correct 13 ms 13952 KB Output is correct
5 Incorrect 168 ms 36344 KB Output isn't correct
6 Halted 0 ms 0 KB -