Submission #235883

#	Time	Username	Problem	Language	Result	Execution time	Memory
235883		kshitij_sodani	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	289 ms	49684 KiB

election_campaign

#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 (stderr)

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
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40