Submission #769724

#	Time	Username	Problem	Language	Result	Execution time	Memory
769724		raysh07	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	212 ms	47332 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

struct Tree {
	vector<vector<int>> adj, lift;	
	vector<int> d, tin, tout;
	int n, timer;
	bool initialized = false;
	bool dfsed = false;

	void init(int nn){
		n = nn;
		adj.resize(n + 1);
		d.resize(n + 1);
		lift.resize(n + 1);
		tin.resize(n + 1);
		tout.resize(n + 1);
		for (int i = 1; i <= n; i++) adj[i].clear();
		for (int i = 0; i <= n; i++) lift[i].resize(20, 0);
		initialized = true;
	}

	void addEdge(int u, int v){
		if (!initialized){
			cout << "STUPID INITIALIZE\n";
			exit(0);
		}
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	void build(){
		for (int j = 1; j < 20; j++){
			for (int i = 1; i <= n; i++){
				lift[i][j] = lift[lift[i][j - 1]][j - 1];
			}
		}
	}

	void dfs(int u, int par){
		tin[u] = ++timer;
		for (int v : adj[u]){
			if (v != par){
				d[v] = d[u] + 1;
				lift[v][0] = u;
				dfs(v, u);
			}
		}
		tout[u] = ++timer;
	}

	void dfs(int root = 1){
		if (!initialized){
			cout << "STUPID INITIALIZE\n";
			exit(0);
		}
		d[root] = 0;
		timer = 0;
		dfs(root, -1);
		build();
		dfsed = true;
	}

	int lca(int a, int b){
		if (!dfsed){
			cout << "STUPID DFS\n";
			exit(0);
		}
		if (d[a] < d[b]) swap(a, b);
		int del = d[a] - d[b];
		for (int i = 0; i < 20; i++) if (del >> i & 1) a = lift[a][i];

		if (a == b) return a;

		for (int i = 19; i >= 0; i--) if (lift[a][i] != lift[b][i]){
			a = lift[a][i];
			b = lift[b][i];
		}
		return lift[a][0];
	}

	int dist(int a, int b){
		return d[a] + d[b] - 2 * d[lca(a, b)];
	}
};

struct info{
	int u, v, w;
};

int n;
const int N = 1e5 + 69;
Tree G;
vector <info> adj[N];
int dp[N][2]; //dp[i][1] = take i, dp[i][0] = not take
int f[2 * N];

void upd(int x, int v){
	for (int i = x; i <= 2 * n; i += i & (-i)) 
		f[i] += v;
} 

int query(int x){
	int res = 0;
	for (int i = x; i; i -= i & (-i)) res += f[i];

	return res;
}

int query(int l, int r){
	return query(r) - query(l - 1);
}

void dfs(int u, int par){
	for (int v : G.adj[u]){
		if (v != par){
			dfs(v, u);
			dp[u][0] += dp[v][1];
			dp[u][1] += dp[v][1];
		}
	}

	for (auto x : adj[u]){
		dp[u][1] = max(dp[u][1], dp[u][0] + x.w - query(G.tin[u], G.tin[x.u]) - query(G.tin[u], G.tin[x.v]));
	}

	upd(G.tin[u], dp[u][1] - dp[u][0]);
	upd(G.tout[u], dp[u][0] - dp[u][1]);
}

void Solve()
{
	cin >> n;

	G.init(n);
	for (int i = 1; i < n; i++){
		int u, v; cin >> u >> v;

		G.addEdge(u, v);
	}

	G.dfs();

	int m; cin >> m;
	while (m--){
		int u, v, w; cin >> u >> v >> w;

		info a1;
		a1.u = u;
		a1.v = v;
		a1.w = w;
		adj[G.lca(u, v)].push_back(a1);
	}

	dfs(1, -1);

	cout << dp[1][1] << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 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