Submission #92924

#	Time	Username	Problem	Language	Result	Execution time	Memory
92924		Dat160601	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	646 ms	31992 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second

const int N = 1e5 + 7;

int n, q, u, v, w, cnt = 0, st[N], ed[N], level[N], dp[N], sum[N];
int par[18][N], it[4 * N], lz[4 * N];
vector <int> edge[N];
vector < pair <int, pair <int, int> > > query[N];

void predfs(int u, int p){
	st[u] = ++cnt;
	for(int v : edge[u]){
		if(v == p) continue;
		level[v] = level[u] + 1;
		par[0][v] = u;
		predfs(v, u);
	}
	ed[u] = cnt;
}

int lca(int u, int v){
	if(level[u] > level[v]) swap(u, v);
	for(int i = 17; i >= 0; i--) if(level[par[i][v]] >= level[u]) v = par[i][v];
	for(int i = 17; i >= 0; i--) if(par[i][u] != par[i][v]) u = par[i][u], v = par[i][v];
	return (u == v ? u : par[0][u]);
}

void lazy(int k, int l, int r){
	if(lz[k] == 0) return;
	it[k] += lz[k];
	if(l != r){
		lz[k << 1] += lz[k];
		lz[k << 1 | 1] += lz[k];
	}
	lz[k] = 0;
}

void update(int k, int l, int r, int L, int R, int val){
	lazy(k, l, r);
	if(l > R || r < L) return;
	if(l >= L && r <= R){
		it[k] += val;
		if(l != r){
			lz[k << 1] += val;
			lz[k << 1 | 1] += val;
		}
		return;
	}
	int mid = (l + r) >> 1;
	update(k << 1, l, mid, L, R, val);
	update(k << 1 | 1, mid + 1, r, L, R, val);
	it[k] = it[k << 1] + it[k << 1 | 1];
}

int get(int k, int l, int r, int pos){
	lazy(k, l, r);
	if(l > pos || r < pos) return 0;
	if(l == r) return it[k];
	int mid = (l + r) >> 1;
	return get(k << 1, l, mid, pos) + get(k << 1 | 1, mid + 1, r, pos);
}

void dfs(int u, int p){
	for(int v : edge[u]){
		if(v == p) continue;
		dfs(v, u);
		sum[u] += dp[v];
	}
	dp[u] = sum[u];
	for(int v : edge[u]){
		if(v == p) continue;
		update(1, 1, n, st[v], ed[v], sum[u] - dp[v]);
	}
	for(int i = 0; i < (int)query[u].size(); i++){
		int a = query[u][i].se.fi, b = query[u][i].se.se;
		int w = query[u][i].fi;
		int lef = get(1, 1, n, st[a]);
		int rig = get(1, 1, n, st[b]);
		dp[u] = max(dp[u], lef + rig + w + sum[a] + sum[b] - sum[u]);
	}
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i < n; i++){
		scanf("%d %d", &u, &v);
		edge[u].pb(v);
		edge[v].pb(u);
	}
	level[1] = 1;
	par[0][1] = 1;
	predfs(1, 1);
	for(int i = 1; i <= 17; i++){
		for(int j = 1; j <= n; j++){
			par[i][j] = par[i - 1][par[i - 1][j]];
		}
	}
	scanf("%d", &q);
	for(int i = 1; i <= q; i++){
		scanf("%d %d %d", &u, &v, &w);
		int lc = lca(u, v);
		query[lc].pb(mp(w, mp(u, v)));
	}
	dfs(1, 1);
	printf("%d", dp[1]);
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
election_campaign.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~
election_campaign.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
election_campaign.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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