oj.uz

Submission #235886

# Submission time Handle Problem Language Result Execution time Memory
235886 2020-05-30T10:16:53 Z kshitij_sodani Election Campaign (JOI15_election_campaign) C++17
10 / 100
 273 ms 49668 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){
	if(k<0){
		while(true){
			continue;
		}
	}
	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:126:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(llo j=0;j<pre[no].size();j++){
              ~^~~~~~~~~~~~~~~
election_campaign.cpp:155: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 11 ms 13696 KB Output is correct
2 Correct 11 ms 13696 KB Output is correct
3 Correct 11 ms 13696 KB Output is correct
4 Correct 12 ms 13952 KB Output is correct
5 Incorrect 154 ms 36472 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 14 ms 13824 KB Output is correct
3 Correct 12 ms 13952 KB Output is correct
4 Correct 253 ms 49668 KB Output is correct
5 Correct 250 ms 49528 KB Output is correct
6 Correct 222 ms 49528 KB Output is correct
7 Correct 259 ms 49656 KB Output is correct
8 Correct 250 ms 49528 KB Output is correct
9 Correct 229 ms 49528 KB Output is correct
10 Correct 252 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 14 ms 13824 KB Output is correct
3 Correct 12 ms 13952 KB Output is correct
4 Correct 253 ms 49668 KB Output is correct
5 Correct 250 ms 49528 KB Output is correct
6 Correct 222 ms 49528 KB Output is correct
7 Correct 259 ms 49656 KB Output is correct
8 Correct 250 ms 49528 KB Output is correct
9 Correct 229 ms 49528 KB Output is correct
10 Correct 252 ms 49528 KB Output is correct
11 Correct 25 ms 15360 KB Output is correct
12 Correct 245 ms 49496 KB Output is correct
13 Correct 255 ms 49628 KB Output is correct
14 Correct 219 ms 49528 KB Output is correct
15 Correct 259 ms 49504 KB Output is correct
16 Correct 251 ms 49528 KB Output is correct
17 Correct 254 ms 49528 KB Output is correct
18 Correct 242 ms 49560 KB Output is correct
19 Correct 214 ms 49528 KB Output is correct
20 Correct 272 ms 49552 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 273 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 11 ms 13696 KB Output is correct
2 Correct 11 ms 13696 KB Output is correct
3 Correct 11 ms 13696 KB Output is correct
4 Correct 12 ms 13952 KB Output is correct
5 Incorrect 154 ms 36472 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

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