Submission #413376

#	Time	Username	Problem	Language	Result	Execution time	Memory
413376		ritul_kr_singh	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	260 ms	41456 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

const int LIM = 1e5;

struct FenwickTree{
	vector<int> a; int n, s;
	void init(int N){ a.resize((n=N)+1); }
	void add(int i, int v){
		for(++i; i<=n; i+=i&-i) a[i] += v;
	}
	int get(int i){
		s = 0;
		for(++i; i>=1; i-=i&-i) s += a[i];
		return s;
	}
} f;

int n, m, t0[LIM], t1[LIM], s[LIM], dp[LIM], dfsTimer = 0;
array<int, 3> a[LIM];
array<int, 18> p[LIM];
vector<int> g[LIM], q[LIM];

void dfs0(int u, int par){
	p[u][0] = par;
	for(int i=0; i<17; ++i) p[u][i+1] = p[p[u][i]][i];

	t0[u] = dfsTimer++;
	for(int v : g[u]) if(v != par) dfs0(v, u);
	t1[u] = dfsTimer++;
}

bool isAncestor(int u, int v){
	return t0[u] <= t0[v] && t1[v] <= t1[u];
}

void dfs1(int u){
	for(int v : g[u]) if(v != p[u][0]) dfs1(v), s[u] += dp[v];
	dp[u] = s[u];
	for(int i : q[u]){
		dp[u] = max(dp[u], f.get(t0[a[i][0]]) + f.get(t0[a[i][1]]) + s[u] + a[i][2]);
	}
	f.add(t0[u], s[u] - dp[u]);
	f.add(t1[u], dp[u] - s[u]);
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int x, y, z; cin >> n;
	for(int i=1; i<n; ++i){
		cin >> x >> y; --x, --y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs0(0, 0);
	f.init(n+n);

	cin >> m;
	for(int i=0; i<m; ++i){
		cin >> x >> y >> a[i][2]; --x, --y;
		a[i][0] = x, a[i][1] = y;

		z = x;
		if(!isAncestor(x, y)){
			for(int j=17; j>=0; --j) while(!isAncestor(p[z][j], y)) z = p[z][j];
			z = p[z][0];
		}

		q[z].push_back(i);
	}

	dfs1(0);

	cout << dp[0];
}

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