oj.uz

Submission #235880

# Submission time Handle Problem Language Result Execution time Memory
235880 2020-05-30T10:05:09 Z kshitij_sodani Election Campaign (JOI15_election_campaign) C++17
10 / 100
 245 ms 38944 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
int n,m;
int ac,bc,dd;
int par[100001][20];
int lev[100001];
vector<int> adj[100001];
int co=0;
int st[100001];
int en[100001];
int dp[100001];
int tree[400001];
int lazy[400001];
vector<pair<pair<int,int>,pair<int,int>>> pre[100001];
vector<int> pre2[100001];
void update(int no,int l,int r,int aa,int bb,int 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{
		int 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];
	}
}
int query(int no,int l,int r,int 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];
	}
	int 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);
	}
}
int dfs(int no,int par2=-1,int 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;
}
int kk(int aa,int k){
	for(int j=19;j>=0;j--){
		if((1<<j)&k){
			aa=par[aa][j];
		}
	}
	return aa;
}
pair<int,pair<int,int>> lca(int aa,int bb){
	int 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(int 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)}};
}
int dfs2(int no,int par2=-1){
	int su=0;
	for(auto j:adj[no]){
		if(j!=par2){
			dfs2(j,no);
			su+=dp[j];
		}
	}
	dp[no]=su;
	for(int j=0;j<pre[no].size();j++){
		pair<pair<int,int>,pair<int,int>> kk=pre[no][j];
		int 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(int 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(int j=1;j<20;j++){
		for(int 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(int i=0;i<m;i++){
		cin>>ac>>bc>>dd;
		pair<int,pair<int,int>> 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 'int dfs(int, int, int)':
election_campaign.cpp:79:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
election_campaign.cpp: In function 'int dfs2(int, int)':
election_campaign.cpp:121:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int 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 10 ms 10496 KB Output is correct
2 Correct 10 ms 10496 KB Output is correct
3 Correct 11 ms 10496 KB Output is correct
4 Correct 11 ms 10624 KB Output is correct
5 Incorrect 150 ms 24440 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 10 ms 10496 KB Output is correct
2 Correct 12 ms 10624 KB Output is correct
3 Correct 11 ms 10752 KB Output is correct
4 Correct 210 ms 38520 KB Output is correct
5 Correct 235 ms 38520 KB Output is correct
6 Correct 219 ms 38520 KB Output is correct
7 Correct 206 ms 38520 KB Output is correct
8 Correct 204 ms 38520 KB Output is correct
9 Correct 189 ms 38520 KB Output is correct
10 Correct 227 ms 38416 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10496 KB Output is correct
2 Correct 12 ms 10624 KB Output is correct
3 Correct 11 ms 10752 KB Output is correct
4 Correct 210 ms 38520 KB Output is correct
5 Correct 235 ms 38520 KB Output is correct
6 Correct 219 ms 38520 KB Output is correct
7 Correct 206 ms 38520 KB Output is correct
8 Correct 204 ms 38520 KB Output is correct
9 Correct 189 ms 38520 KB Output is correct
10 Correct 227 ms 38416 KB Output is correct
11 Correct 23 ms 11776 KB Output is correct
12 Correct 217 ms 38704 KB Output is correct
13 Correct 206 ms 38776 KB Output is correct
14 Correct 222 ms 38820 KB Output is correct
15 Correct 200 ms 38904 KB Output is correct
16 Correct 226 ms 38776 KB Output is correct
17 Correct 214 ms 38776 KB Output is correct
18 Correct 211 ms 38904 KB Output is correct
19 Correct 187 ms 38944 KB Output is correct
20 Correct 216 ms 38776 KB Output is correct

Subtask #4
0 / 30.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10496 KB Output is correct
2 Correct 10 ms 10496 KB Output is correct
3 Correct 11 ms 10496 KB Output is correct
4 Correct 11 ms 10624 KB Output is correct
5 Incorrect 150 ms 24440 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10496 KB Output is correct
2 Correct 10 ms 10496 KB Output is correct
3 Correct 11 ms 10496 KB Output is correct
4 Correct 11 ms 10624 KB Output is correct
5 Incorrect 150 ms 24440 KB Output isn't correct
6 Halted 0 ms 0 KB -