Submission #64290

#	Time	Username	Problem	Language	Result	Execution time	Memory
64290		RezwanArefin01	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	550 ms	153264 KiB

election_campaign

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

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 1e5 + 10; 

vector<int> adj[N], q[N];  
int a[N], b[N], c[N], n, m; 
int p[N][19], L[N], in[N], out[N], tym; 
ll bit[N + N], dp[N];

void dfs(int u, int par) {
	p[u][0] = par; 
	for(int i = 1; i <= 18; i++) 
		p[u][i] = p[p[u][i - 1]][i - 1]; 
	L[u] = L[par] + 1; 
	in[u] = ++tym; 
	for(int v : adj[u]) if(v - par) 
		dfs(v, u); 
	out[u] = ++tym; 
}

int lca(int u, int v) {
	if(L[u] < L[v]) swap(u, v); 
	for(int i = 18; i >= 0; i--) 
		if(L[p[u][i]] >= L[v]) 
			u = p[u][i];
	if(u == v) return u; 
	for(int i = 18; i >= 0; i--)
		if(p[u][i] - p[v][i]) 
			u = p[u][i], v = p[v][i];
	return p[u][0]; 
}

void update(int x, int v) {
	for(; x <= tym; x += x & -x) 
		bit[x] += v; 
}

ll read(int x) {
	ll ret = 0;
	for(; x > 0; x -= x & -x) 
		ret += bit[x];
	return ret;
}

void solve(int u, int par) {
	for(int v : adj[u]) if(v - par) {
		solve(v, u); 
		update(in[u], dp[v]);
		update(out[u], -dp[v]); 
	}
	ll x = read(in[u]), y = read(in[par]);
	for(int i : q[u]) {
		ll tot = read(in[a[i]]) + read(in[b[i]]) - x - y; 
		dp[u] = max(dp[u], tot + c[i]); 
	}
	dp[u] = max(dp[u], x - y);
	update(in[u], -dp[u]); 
	update(out[u], dp[u]); 
}
int main(int argc, char const *argv[]) {
	scanf("%d", &n);
	for(int i = 1; i < n; i++) {
		int u, v; 
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	} dfs(1, 0); 

	scanf("%d", &m);
	for(int i = 1; i <= m; i++) {
		scanf("%d %d %d", &a[i], &b[i], &c[i]); 
		int l = lca(a[i], b[i]);
		q[l].push_back(i);  
	}
	solve(1, 0); 
	printf("%lld\n", dp[1]);
}

Compilation message (stderr)

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