Submission #399213

#	Time	Username	Problem	Language	Result	Execution time	Memory
399213		keta_tsimakuridze	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	429 ms	43196 KiB

election_campaign

#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=1e5+5,mod=1e9+7;
int t,tmin[N],tmout[N],tree[4*N],g[2],timer,dp[N][2],n,m,ans,par[N][20],Lg;
vector<int>V[N];
vector<pair<int,pair<int,int> > >q[N];
string s;
void dfs(int u,int p) {
	timer++;
	tmin[u]=timer;	
	par[u][0]=p;
	for(int i=1;i<=Lg;i++) par[u][i]=par[par[u][i-1]][i-1];
	for(int i=0;i<V[u].size();i++){
		if(V[u][i]==p) continue;
		dfs(V[u][i],u);
	}
	tmout[u]=timer;
}
bool check(int u,int v){
	if(tmin[u]<=tmin[v] && tmout[u]>=tmout[v]) return 1;
	return 0;
}
int find_lca(int u,int v){
	if(check(u,v)) return u;
	if(check(v,u)) return v;
	for(int i=Lg;i>=0;i--){
		if(par[u][i] && !check(par[u][i],v)) u=par[u][i];
	}
	return par[u][0];
}
int up(int u,int v){
	for(int i=Lg;i>=0;i--){
		if(par[v][i] && !check(par[v][i],u)) v=par[v][i];
	}
	return v;
}
void update(int u,int start,int end,int l,int r,int val){
	if(l>end || r<start) return;
	if(start<=l && r<=end) {
		tree[u]+=val;
		return;
	}
	int mid=(l+r)/2;
	update(2*u,start,end,l,mid,val);
	update(2*u+1,start,end,mid+1,r,val);
}
void getans(int u,int ind,int l,int r,int b){
	if(l>ind || r<ind) return;
	g[b]+=tree[u];
	if(l==r) return;
	int mid=(l+r)/2;
	getans(2*u,ind,l,mid,b);
	getans(2*u+1,ind,mid+1,r,b);
}
void solve(int u,int p){ 
	for(int i=0;i<V[u].size();i++){
		if(V[u][i]==p) continue;
		solve(V[u][i],u);
		dp[u][0]+=dp[V[u][i]][1];
	}
	dp[u][1]=dp[u][0];
	for(int i=0;i<q[u].size();i++){
		int par1,par2,c=0;	
		g[1]=g[0]= 0; 	
		getans(1,tmin[q[u][i].s.f],1,n,0);  
		getans(1,tmin[q[u][i].s.s],1,n,1);
		if(q[u][i].s.f==u) par1 = 0;
		else c+=g[0],par1 = up(u,q[u][i].s.f); 
		if(q[u][i].s.s==u) par2 = 0;
		else c+=g[1],par2 = up(u,q[u][i].s.s);
		dp[u][1] = max(dp[u][1],q[u][i].f+c+dp[u][0] - dp[par1][1] - dp[par2][1]);
		ans=max(ans,dp[u][1]);
	} 
	for(int i=0;i<V[u].size();i++){
		if(V[u][i]==p) continue;
		update(1,tmin[V[u][i]],tmout[V[u][i]],1,n,dp[u][0]-dp[V[u][i]][1]);
	} 
	update(1,tmin[u],tmin[u],1,n,dp[u][0]);
}
 main(){
	// t=1;
	cin >> n;
	Lg=log2(n)+1;
	for(int i=2;i<=n;i++){
		int u,v;
		cin>>u>>v;
		V[u].push_back(v);
		V[v].push_back(u);
	}
	dfs(1,0);
	cin>>m;
	for(int i=1;i<=m;i++){
		int u,v,c;
		cin>>u>>v>>c; 
		q[find_lca(u,v)].push_back({c,{u,v}});
	}
	solve(1,0);
	cout<<ans;
}

Compilation message (stderr)

election_campaign.cpp: In function 'void dfs(long long int, long long int)':
election_campaign.cpp:16:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
election_campaign.cpp: In function 'void solve(long long int, long long int)':
election_campaign.cpp:59:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
election_campaign.cpp:65:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=0;i<q[u].size();i++){
      |              ~^~~~~~~~~~~~
election_campaign.cpp:77:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
election_campaign.cpp: At global scope:
election_campaign.cpp:83:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   83 |  main(){
      |       ^

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40