Submission #329764

#	Time	Username	Problem	Language	Result	Execution time	Memory
329764		GioChkhaidze	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	346 ms	33260 KiB

election_campaign

#include <bits/stdc++.h>

#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define ll long long
#define pb push_back
#define F first
#define S second

using namespace std;

const int N=1e5+5;

int n,q,depth,timer;
ll S[N],dp[N],t[4*N];
int in[N],out[N],dep[N],P[N][19];

vector < int > v[N];
vector < pair < pair < int , int > , int > > E[N];

bool anc(int a,int b) {
	return (in[a]<=in[b] && out[b]<=out[a]);
}

int LCA(int a,int b) {
	if (dep[a]>dep[b]) swap(a,b);
	if (anc(a,b)) return a;
	for (int i=17; i>=0; i--) 
		if (!anc(P[a][i],b)) a=P[a][i];
	return P[a][0];
}

void Dfs(int x,int p) {
	P[x][0]=p;
	in[x]=++timer;
	dep[x]=++depth;
	for (int i=0; i<v[x].size(); i++) {
		int to=v[x][i];
		if (to==p) continue;
		Dfs(to,x);
	}
	out[x]=timer;
	--depth;
}

void Upd(Tree,int L,int R,ll dl) {
	if (r<L || R<l) return ;
	if (L<=l && r<=R) {
		t[h]+=dl;
		return ;
	} 
	
	Upd(Left,L,R,dl);
	Upd(Right,L,R,dl);
}

ll get(Tree,int id) {
	if (id<l || r<id) return 0;
	if (l==id && r==id) return t[h];
	return get(Left,id)+get(Right,id)+t[h];
}

void Ufs(int x,int p) {
	for (int i=0; i<v[x].size(); i++) {
		int to=v[x][i];
		if (to==p) continue;
		Ufs(to,x);
		S[x]+=dp[to];
	}
	
	dp[x]=S[x];
	for (int i=0; i<E[x].size(); i++) {
		int a=E[x][i].F.F,b=E[x][i].F.S;
		ll cost=E[x][i].S;
		
		if (b!=x) 
			cost+=get(1,1,n,in[a])+get(1,1,n,in[b]);
				else
			cost+=get(1,1,n,in[a]);		

		dp[x]=max(dp[x],S[x]+cost);
	}
	
	Upd(1,1,n,in[x],out[x],S[x]-dp[x]);
} 

main () {
	cin>>n;
	for (int i=1; i<n; i++) {
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}
	
	Dfs(1,1);
	
	for (int j=1; j<=17; j++)
		for (int i=1; i<=n; i++) 
			P[i][j]=P[P[i][j-1]][j-1];
	
	cin>>q;
	for (int i=1; i<=q; i++) {
		int a,b,c;
		cin>>a>>b>>c;
		if (dep[a]<dep[b]) swap(a,b);
		E[LCA(a,b)].pb({{a,b},c});
	}
	
	Ufs(1,1);
	
	cout<<dp[1]<<"\n";
}

Compilation message (stderr)

election_campaign.cpp: In function 'void Dfs(int, int)':
election_campaign.cpp:38:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int i=0; i<v[x].size(); i++) {
      |                ~^~~~~~~~~~~~
election_campaign.cpp: In function 'void Ufs(int, int)':
election_campaign.cpp:65:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for (int i=0; i<v[x].size(); i++) {
      |                ~^~~~~~~~~~~~
election_campaign.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for (int i=0; i<E[x].size(); i++) {
      |                ~^~~~~~~~~~~~
election_campaign.cpp: At global scope:
election_campaign.cpp:88:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | 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