Submission #170820

#	Time	Username	Problem	Language	Result	Execution time	Memory
170820		ZwariowanyMarcin	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	290 ms	31216 KiB

election_campaign

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;	

const int nax = 1e5 + 11;
const int LOG = 16;
const int pod = (1 << 17);

int n;
int a, b;
vector <int> v[nax];
int m, c;
int pre[nax];
int post[nax];
int h[nax];
int jump[nax][LOG + 1];
int cnt;

void dfs(int u, int p) {
	h[u] = h[p] + 1;
	jump[u][0] = p;
	pre[u] = cnt++;
	for(auto it : v[u]) 
		if(it != p)
			dfs(it, u);
	post[u] = cnt;
}

int lca(int x, int y) {
	if(h[x] < h[y])
		swap(x, y);
	for(int i = LOG; 0 <= i; --i)
		if(h[y] <= h[x] - (1 << i))
			x = jump[x][i];
	if(x == y)
		return x;
	for(int i = LOG; 0 <= i; --i) 
		if(jump[x][i] != jump[y][i]) {
			x = jump[x][i];
			y = jump[y][i];
		}
	return jump[x][0];
}

struct gao {
	int a, b, c;
};

vector <gao> V[nax];

struct seg {
	int t[2 * pod];
	
	void init() {
		for(int i = 0; i < 2 * pod; ++i)
			t[i] = 0;
	}
	
	void add(int l, int r, int c) {
		for(l += pod, r += pod; l < r; l /= 2, r /= 2) {
			if(l & 1)
				t[l++] += c;
			if(r & 1)
				t[--r] += c;
		}
	}
	
	int query(int x) {
		int sum = 0;
		x += pod;
		while(x) {
			sum += t[x];
			x /= 2;
		}
		return sum;
	}
} child, node;

int dp[nax];

void solve(int u, int p) {
	int Sum = 0;
	for(auto it : v[u])
		if(it != p) {
			solve(it, u);
			Sum += dp[it];
		}
	child.add(pre[u], post[u], Sum);
	dp[u] = Sum;
	for(auto it : V[u]) {
		int w = child.query(pre[it.a]) + child.query(pre[it.b]) - Sum - node.query(pre[it.a]) - node.query(pre[it.b]) + it.c;
		dp[u] = max(dp[u], w);
	}
	node.add(pre[u], post[u], dp[u]);
}

int main() {
	child.init();
	node.init();
	scanf("%d", &n);
	for(int i = 1; i < n; ++i) {
		scanf("%d %d", &a, &b);
		v[a].pb(b);
		v[b].pb(a);
	}
	dfs(1, 0);

	for(int j = 1; j <= LOG; ++j)
		for(int i = 1; i <= n; ++i)
			jump[i][j] = jump[jump[i][j - 1]][j - 1];
	
	scanf("%d", &m);
	
	for(int i = 1; i <= m; ++i) {
		scanf("%d %d %d", &a, &b, &c);
		V[lca(a, b)].pb({a, b, c});
	}
	
	solve(1, 0);
	
	printf("%d\n", dp[1]);
	
	
	return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
election_campaign.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~
election_campaign.cpp:120:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
election_campaign.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &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