Submission #1117279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117279		Peter2017	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	117 ms	27220 KiB

election_campaign

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pill pair<int,ll>
#define mem(a, b) memset(a, b, sizeof(a))
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define name "test"

using namespace std;

const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;

template <typename T1, typename T2> bool maxi(T1 &a, T2 b){if (a < b){a = b; return 1;} return 0;}
template <typename T1, typename T2> bool mini(T1 &a, T2 b){if (a > b){a = b; return 1;} return 0;}

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

int n;
int m;
ll f[N];
vector<int> adj[N];
vector<item> campaign[N];

struct FenwickTree{
	int n;
	ll val[N];

	FenwickTree(){};

	void update(int idx, ll x){
		assert(idx > 0);
		for (; idx <= n; idx += idx & -idx)
			val[idx] += x;
	}

	ll get(int idx){
		ll res = 0;
		for (; idx; idx -= idx & -idx)
			res += val[idx];
		return res;
	}

	ll get(int l, int r){
		return get(r) - get(l - 1);
	}
} ft;

struct HLD{
	int cntDfs;
	int inv[N];
	int cnt[N];
	int idx[N];
	int par[N];
	int head[N];
	int high[N];
	int big_child[N];
	long long f[N];
	long long g[N];

	HLD(){};

	void dfs(int u, int pre){
		int C = 0;
		cnt[u] = 1;
		head[u] = u;
		for (int v : adj[u]) if (v != pre){
			dfs(v, u);
			par[v] = u;
			cnt[u] += cnt[v];
			if (cnt[C] <= cnt[v]) C = v;
		}
		big_child[u] = C;
	}

	void indexing(int u, int pre){
		idx[u] = ++cntDfs;
		inv[cntDfs] = u;
		if (!big_child[u]) return;
		head[big_child[u]] = head[u];
		high[big_child[u]] = high[u];
		indexing(big_child[u], u);
		for (int v : adj[u]) if (v != pre && v != big_child[u]){
			high[v] = high[u] + 1;
			indexing(v, u);
		}
	}

	int LCA(int u, int v){
		if (high[u] < high[v]) swap(u, v);
		while (high[u] > high[v]) u = par[head[u]];
		while (head[u] != head[v]){
			u = par[head[u]];
			v = par[head[v]];
		}
		return idx[u] < idx[v] ? u : v;
	}

	void init(){
		dfs(1, 0);
		indexing(1, 0);
	}

	ll get(int u, int v, int nxtU, int ancestor, bool debug){
		if (high[u] < high[v]) swap(u, v);
		ll ans = 0;
		while (high[u] > high[v]){
			if (head[inv[idx[u] + 1]] == head[u]) ans += f[inv[idx[u] + 1]];
			ans += ft.get(idx[head[u]], idx[u]) - f[head[u]];
			u = par[head[u]];
		}
		while (head[u] != head[v]){
			if (head[inv[idx[u] + 1]] == head[u]) ans += f[inv[idx[u] + 1]];
			if (head[inv[idx[v] + 1]] == head[v]) ans += f[inv[idx[v] + 1]];
			ans += ft.get(idx[head[u]], idx[u]) - f[head[u]];
			ans += ft.get(idx[head[v]], idx[v]) - f[head[v]];
			u = par[head[u]];
			v = par[head[v]];
		}
		if (idx[u] > idx[v]) swap(u, v);
		ans += ft.get(idx[u], idx[v]);
		if (head[inv[idx[v] + 1]] == head[v]) ans += f[inv[idx[v] + 1]];
		return ans;
	}

	void dfsAns(int u, int pre){
		int nxtU = -1;
		if (idx[u] < n && head[inv[idx[u] + 1]] == head[u])
			nxtU = inv[idx[u] + 1];
		for (int v : adj[u]) if (v != pre){
			dfsAns(v, u);
			f[u] += f[v];
		}
		maxi(f[u], g[u]);
		ft.update(idx[u], g[u]);
		for (auto [a, b, w] : campaign[u]){
			maxi(f[u], get(a, b, nxtU, u, 0) + w);
		}
		if (head[par[u]] != head[u]){
			g[par[u]] += f[u];
		}
	}

	void solve(){
		ft.n = n;
		dfsAns(1, 0);
		cout << f[1];
	}
} tree;

void load(){
    cin.tie(0)->sync_with_stdio(0);
    if (fopen(name".inp", "r")){
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
}

void solve(){
	cin >> n;
	for (int i = 1; i < n; i++){
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	tree.init();
	cin >> m;
	for (int i = 1; i <= m; i++){
		int u, v, w; cin >> u >> v >> w;
		campaign[tree.LCA(u, v)].push_back({u, v, w});
	}
	tree.solve();
}

int main(){
    load();
    solve();
}

Compilation message (stderr)

election_campaign.cpp: In member function 'void HLD::dfsAns(int, int)':
election_campaign.cpp:143:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  143 |   for (auto [a, b, w] : campaign[u]){
      |             ^
election_campaign.cpp: In function 'void load()':
election_campaign.cpp:161:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:162:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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