Submission #26471

#	Time	Username	Problem	Language	Result	Execution time	Memory
26471		rubabredwan	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	336 ms	45332 KiB

election_campaign

/*  Bismillahir Rahmanir Rahim  */

#include <bits/stdc++.h>

#define debug(x) cout << #x << ' ' << x << endl

using namespace std;

const int N = 200005;

struct data{
	int u, v, c;
	data () {}
	data (int _u, int _v, int _c){
		u = _u, v = _v, c = _c;
	}
};

struct BIT{
	int t[N], n;
	void init(int _n){
		n = _n;
		memset(t, 0, sizeof(t));
	}
	void update(int pos, int val){
		while(pos <= n){
			t[pos] += val;
			pos += pos & -pos;
		}
	}
	int get(int pos){
		int ret = 0;
		while(pos){
			ret += t[pos];
			pos -= pos & -pos;
		}
		return ret;
	}
	int get(int l, int r){
		return get(r) - get(l - 1);
	}
};

int n;
int m; 
int A[N], B[N], C[N];
int dp[N];
vector <data> cnd[N];
vector <int> g[N];
int dep[N];
int pa[N][18];
int in[N], out[N], t;
BIT t1, t2;

void dfs(int at, int par){
	in[at] = ++t;
	pa[at][0] = par;
	for(int i = 1; i <= 16; ++i) pa[at][i] = pa[ pa[at][i-1] ][ i-1 ];
	for(auto u : g[at]){
		if(u != par){
			dep[u] = dep[at] + 1;
			dfs(u, at);
		}
	}
	out[at] = ++t;
}

int lca(int a, int b){
	if(dep[a] < dep[b]) swap(a, b);
	for(int i = 16; i >= 0; --i) if(dep[a] - (1 << i) >= dep[b]) a = pa[a][i];
	if(a == b) return a;
	for(int i = 16; i >= 0; --i) if(pa[a][i] != pa[b][i]) a = pa[a][i], b = pa[b][i];
	return pa[a][0];
}

void solve(int at, int par){
	int child_sum = 0;
	for(auto u : g[at]){
		if(u == par) continue;
		solve(u, at);
		dp[at] += dp[u];
		child_sum += dp[u];
	}
	for(auto f : cnd[at]){
		int u = f.u, v = f.v, c = f.c;
		int sum = child_sum;
		if(u == at){
			sum += t2.get(in[v]) - t1.get(in[v]);
		}
		else{
			sum += t2.get(in[u]) - t1.get(in[u]);
			sum += t2.get(in[v]) - t1.get(in[v]);
		}
		dp[at] = max(dp[at], c + sum);
	}
	t1.update(in[at], +dp[at]);
	t1.update(out[at], -dp[at]);
	t2.update(in[at], +child_sum);
	t2.update(out[at], -child_sum);
}

int main(){
	int x, y;
	scanf("%d", &n);
	for(int i = 1; i < n; ++i){
		scanf("%d %d", &x, &y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1, 0);
	scanf("%d", &m);
	for(int i = 1; i <= m; ++i){
		scanf("%d %d %d", &A[i], &B[i], &C[i]);
		int lc = lca(A[i], B[i]);
		if(B[i] == lc) swap(A[i], B[i]);
		cnd[lc].push_back(data(A[i], B[i], C[i]));
	}
	t1.init(2 * n);
	t2.init(2 * n);
	solve(1, 0);
	printf("%d\n", dp[1]);
	return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:104:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
election_campaign.cpp:106:25: 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:111:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
                 ^
election_campaign.cpp:113:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &A[i], &B[i], &C[i]);
                                         ^

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