oj.uz

Submission #235881

# Submission time Handle Problem Language Result Execution time Memory
235881 2020-05-30T10:07:00 Z kshitij_sodani Election Campaign (JOI15_election_campaign) C++17
10 / 100
 282 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);
	//	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 12 ms 13696 KB Output is correct
4 Correct 13 ms 13952 KB Output is correct
5 Incorrect 174 ms 36476 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 13 ms 13696 KB Output is correct
2 Correct 12 ms 13696 KB Output is correct
3 Correct 13 ms 13952 KB Output is correct
4 Correct 266 ms 49528 KB Output is correct
5 Correct 267 ms 49528 KB Output is correct
6 Correct 222 ms 49528 KB Output is correct
7 Correct 243 ms 49528 KB Output is correct
8 Correct 268 ms 49528 KB Output is correct
9 Correct 222 ms 49684 KB Output is correct
10 Correct 282 ms 49528 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13696 KB Output is correct
2 Correct 12 ms 13696 KB Output is correct
3 Correct 13 ms 13952 KB Output is correct
4 Correct 266 ms 49528 KB Output is correct
5 Correct 267 ms 49528 KB Output is correct
6 Correct 222 ms 49528 KB Output is correct
7 Correct 243 ms 49528 KB Output is correct
8 Correct 268 ms 49528 KB Output is correct
9 Correct 222 ms 49684 KB Output is correct
10 Correct 282 ms 49528 KB Output is correct
11 Correct 25 ms 15360 KB Output is correct
12 Correct 237 ms 49528 KB Output is correct
13 Correct 258 ms 49656 KB Output is correct
14 Correct 235 ms 49608 KB Output is correct
15 Correct 246 ms 49656 KB Output is correct
16 Correct 230 ms 49656 KB Output is correct
17 Correct 265 ms 49528 KB Output is correct
18 Correct 247 ms 49528 KB Output is correct
19 Correct 241 ms 49576 KB Output is correct
20 Correct 269 ms 49592 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 277 ms 41060 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 12 ms 13696 KB Output is correct
4 Correct 13 ms 13952 KB Output is correct
5 Incorrect 174 ms 36476 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 12 ms 13696 KB Output is correct
4 Correct 13 ms 13952 KB Output is correct
5 Incorrect 174 ms 36476 KB Output isn't correct
6 Halted 0 ms 0 KB -