oj.uz

Submission #235898

# Submission time Handle Problem Language Result Execution time Memory
235898 2020-05-30T10:32:00 Z kshitij_sodani Election Campaign (JOI15_election_campaign) C++17
10 / 100
 293 ms 49784 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==kk.b.b){
			while(true){
				continue;
			}
		}
		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:156:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 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 12 ms 13952 KB Output is correct
5 Incorrect 171 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 12 ms 13696 KB Output is correct
3 Correct 13 ms 14080 KB Output is correct
4 Correct 245 ms 49528 KB Output is correct
5 Correct 263 ms 49528 KB Output is correct
6 Correct 255 ms 49528 KB Output is correct
7 Correct 259 ms 49784 KB Output is correct
8 Correct 239 ms 49528 KB Output is correct
9 Correct 229 ms 49656 KB Output is correct
10 Correct 283 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 12 ms 13696 KB Output is correct
3 Correct 13 ms 14080 KB Output is correct
4 Correct 245 ms 49528 KB Output is correct
5 Correct 263 ms 49528 KB Output is correct
6 Correct 255 ms 49528 KB Output is correct
7 Correct 259 ms 49784 KB Output is correct
8 Correct 239 ms 49528 KB Output is correct
9 Correct 229 ms 49656 KB Output is correct
10 Correct 283 ms 49528 KB Output is correct
11 Correct 27 ms 15360 KB Output is correct
12 Correct 259 ms 49528 KB Output is correct
13 Correct 252 ms 49528 KB Output is correct
14 Correct 240 ms 49656 KB Output is correct
15 Correct 246 ms 49528 KB Output is correct
16 Correct 214 ms 49656 KB Output is correct
17 Correct 241 ms 49528 KB Output is correct
18 Correct 293 ms 49528 KB Output is correct
19 Correct 224 ms 49528 KB Output is correct
20 Correct 257 ms 49656 KB Output is correct

Subtask #4
0 / 30.0

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