Submission #25412

#	Time	Username	Problem	Language	Result	Execution time	Memory
25412		khsoo01	Election Campaign (JOI15_election_campaign)	C++11	100 / 100	536 ms	39880 KiB

election_campaign

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> tp;
const ll N = 100005, L = 20;

ll n, cc, s[N], e[N], dep[N], par[L][N], dt[N];

vector<ll> adj[N];
vector<tp> v[N];

struct segtree {
	ll val[4*N], lim;
	void init () {
		for(lim = 1; lim <= n; lim <<= 1);
	}
	void upd (ll S, ll E, ll V) {
		S += lim; E += lim;
		while(S <= E) {
			if(S%2==1) val[S++] += V;
			if(E%2==0) val[E--] += V;
			S>>=1; E>>=1;
		}
	}
	ll get (ll P) {
		ll ret = 0; P += lim;
		while(P) {ret += val[P]; P>>=1;}
		return ret;
	}
} seg;

ll getlca (ll A, ll B) {
	if(dep[A] < dep[B]) swap(A, B);
	for(ll i=L;i--;) {
		if(dep[A]-dep[B]>=(1<<i)) A = par[i][A];
	}
	if(A == B) return A;
	for(ll i=L;i--;) {
		if(par[i][A] != par[i][B]) {
			A = par[i][A]; B = par[i][B];
		}
	}
	return par[0][A];
}

void calc (ll C, ll P) {
	s[C] = ++cc;
	dep[C] = dep[P] + 1;
	par[0][C] = P;
	for(auto &T : adj[C]) {
		if(T == P) continue;
		calc(T, C);
	}
	e[C] = cc;
}

void solve (ll C, ll P) {
	ll def = 0;
	for(auto &T : adj[C]) {
		if(T == P) continue;
		solve(T, C);
		def += dt[T];
	}
	dt[C] = def;
	for(auto &T : v[C]) {
		ll A, B, V; tie(A, B, V) = T;
		dt[C] = max(dt[C], def+seg.get(s[A])+seg.get(s[B])+V);
	}
	seg.upd(s[C], e[C], def-dt[C]);
}

int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<n;i++){
		ll A, B;
		scanf("%lld%lld",&A,&B);
		adj[A].push_back(B);
		adj[B].push_back(A);
	}
	calc(1, 0);
	for(ll k=1;k<L;k++) {
		for(ll i=1;i<=n;i++) {
			par[k][i] = par[k-1][par[k-1][i]];
		}
	}
	ll M;
	scanf("%lld",&M);
	for(ll i=1;i<=M;i++) {
		ll A, B, C;
		scanf("%lld%lld%lld",&A,&B,&C);
		ll X = getlca(A, B);
		v[X].push_back(make_tuple(A, B, C));
	}
	seg.init();
	solve(1, 0);
	printf("%lld\n",dt[1]);
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
                  ^
election_campaign.cpp:77:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&A,&B);
                          ^
election_campaign.cpp:88:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&M);
                  ^
election_campaign.cpp:91:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld",&A,&B,&C);
                                 ^

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