Submission #25408

#	Time	Username	Problem	Language	Result	Execution time	Memory
25408		kdh9949	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	606 ms	35316 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;

struct Q{ int x, y, c; };

int n, m, d[100010], dp[100010], ps[100010], pe[100010], cnt, sp[17][100010];
vector<int> e[100010], ch[100010];
vector<Q> q[100010];

const int sz = 131072;
struct Seg{
	int dat[2 * sz];
	void upd(int s, int e, int x){
		for(s += sz, e += sz; s <= e; s /= 2, e /= 2){
			if(s % 2 == 1) dat[s++] += x;
			if(e % 2 == 0) dat[e--] += x;
		}
	}
	int get(int x){
		int ret = 0;
		for(x += sz; x; x /= 2) ret += dat[x];
		return ret;
	}
} S, T;

void g(int x, int p){
	ps[x] = ++cnt;
	sp[0][x] = p;
	d[x] = d[p] + 1;
	for(int i = 1; i < 17; i++) sp[i][x] = sp[i - 1][sp[i - 1][x]];
	for(auto &i : e[x]){
		if(i != p){
			ch[x].push_back(i);
			g(i, x);
		}
	}
	pe[x] = cnt;
}

int lca(int x, int y){
	if(d[x] < d[y]) swap(x, y);
	for(int i = 16; i >= 0; i--) if(d[sp[i][x]] >= d[y]) x = sp[i][x];
	if(x == y) return x;
	for(int i = 16; i >= 0; i--){
		if(sp[i][x] != sp[i][y]){ x = sp[i][x]; y = sp[i][y]; }
	}
	return sp[0][x];
}

void f(int x){
	int cs = 0;
	for(auto &i : ch[x]){
		f(i);
		cs += dp[i];
	}
	for(auto &i : ch[x]) T.upd(ps[i], pe[i], i);
	int ret = cs;
	for(auto &i : q[x]){
		int cret = cs;
		if(i.x != x) cret += S.get(ps[i.x]) - dp[T.get(ps[i.x])];
		if(i.y != x) cret += S.get(ps[i.y]) - dp[T.get(ps[i.y])];
		ret = max(ret, cret + i.c);
	}
	for(auto &i : ch[x]){
		S.upd(ps[x] + 1, ps[i] - 1, dp[i]);
		S.upd(pe[i] + 1, pe[x], dp[i]);
		T.upd(ps[i], pe[i], -i);
	}
	S.upd(ps[x], ps[x], cs);
	dp[x] = ret;
}

int main(){
	scanf("%d", &n);
	for(int i = 0, x, y; i < n - 1; i++){
		scanf("%d%d", &x, &y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	g(1, 1);
	scanf("%d", &m);
	for(int x, y, z; m--; ){
		scanf("%d%d%d", &x, &y, &z);
		q[lca(x, y)].push_back({x, y, z});
	}
	f(1);
	printf("%d\n", dp[1]);
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:74:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
election_campaign.cpp:76:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
                        ^
election_campaign.cpp:81:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
                 ^
election_campaign.cpp:83:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   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