Submission #106176

#	Time	Username	Problem	Language	Result	Execution time	Memory
106176		cki86201	Election Campaign (JOI15_election_campaign)	C++11	100 / 100	445 ms	32560 KiB

election_campaign

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb push_back
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int N, M;
vector <int> E[100010];
int In[100010][3];

vector <int> qs[100010];
int ST[100010], EN[100010], cs;
int dep[100010];
int up[100010][20];

void pdfs(int x, int fa) {
	ST[x] = ++cs;
	for(int e : E[x]) if(e != fa) {
		dep[e] = dep[x] + 1;
		up[e][0] = x;
		for(int i=1;i<20;i++) up[e][i] = up[ up[e][i-1] ][i-1];
		pdfs(e, x);
	}
	EN[x] = cs;
}

int get_lca(int x, int y) {
	if(dep[x] < dep[y]) swap(x, y);
	rep(i, 20) if(1<<i & (dep[x] - dep[y])) x = up[x][i];
	for(int i=19;i>=0;i--) if(up[x][i] != up[y][i]) x = up[x][i], y = up[y][i];
	return x == y ? x : up[x][0];
}

ll T[100010];
void update_s(int x, ll v) {
	int l = ST[x], r = EN[x];
	for(int i=l;i<=N;i+=(i&-i)) T[i] += v;
	for(int i=r+1;i<=N;i+=(i&-i)) T[i] -= v;
}
ll read(int x) {
	ll res = 0;
	for(int i=ST[x];i;i-=(i&-i)) res += T[i];
	return res;
}

ll A[100010], B[100010];

void dfs(int x, int fa) {
	for(int e : E[x]) if(e != fa) {
		dfs(e, x);
		B[x] += A[e];
	}
	A[x] = B[x];
	for(int e : qs[x]) {
		int u = In[e][0], v = In[e][1], cost = In[e][2];
		ll val = B[x] + cost - read(u) - read(v);
		if(A[x] < val) A[x] = val;
	}
	update_s(x, A[x] - B[x]);
}

int main() {
	scanf("%d", &N);
	for(int i=1;i<N;i++) {
		int x, y; scanf("%d%d", &x, &y);
		E[x].pb(y);
		E[y].pb(x);
	}
	scanf("%d", &M);
	pdfs(1, -1);
	for(int i=1;i<=M;i++) {
		int x, y, z; scanf("%d%d%d", &x, &y, &z);
		int lca = get_lca(x, y);
		qs[lca].pb(i);
		In[i][0] = x; In[i][1] = y; In[i][2] = z;
	}
	dfs(1, -1);
	printf("%lld\n", A[1]);
	
	return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
election_campaign.cpp:90:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
election_campaign.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &M);
  ~~~~~^~~~~~~~~~
election_campaign.cpp:97:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, z; scanf("%d%d%d", &x, &y, &z);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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