Submission #1117270

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1117270	2024-11-23T07:39:34 Z	Peter2017	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	94 ms	30536 KB

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;
		bool pass = (nxtU == -1);
		if (idx[u] < n && u != ancestor){
			if (head[inv[idx[u] + 1]] == head[u]){
				ans += f[inv[idx[u] + 1]];
			}
		}
		if (idx[v] < n && v != ancestor){
			if (head[inv[idx[v] + 1]] == head[v]){
				ans += f[inv[idx[v] + 1]];
			}
		}
		while (high[u] > high[v]){
			if (nxtU != -1) pass |= (idx[head[u]] <= idx[nxtU] && idx[nxtU] <= idx[u]);
			ans += ft.get(idx[head[u]], idx[u]) - f[head[u]];
			u = par[head[u]];
		}
		while (head[u] != head[v]){
			if (nxtU != -1) pass |= (idx[head[u]] <= idx[nxtU] && idx[nxtU] <= idx[u]);
			if (nxtU != -1) pass |= (idx[head[v]] <= idx[nxtU] && idx[nxtU] <= idx[v]);
			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]);
		pass |= (idx[u] <= idx[nxtU] && idx[nxtU] <= idx[v]);
		if (!pass) ans += f[nxtU];
		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

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

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	8528 KB	Output is correct
2	Correct	2 ms	8672 KB	Output is correct
3	Incorrect	2 ms	8528 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	8528 KB	Output is correct
2	Correct	2 ms	8528 KB	Output is correct
3	Correct	2 ms	8784 KB	Output is correct
4	Correct	58 ms	30024 KB	Output is correct
5	Correct	60 ms	30028 KB	Output is correct
6	Correct	58 ms	30024 KB	Output is correct
7	Correct	62 ms	30200 KB	Output is correct
8	Correct	59 ms	30220 KB	Output is correct
9	Correct	71 ms	30080 KB	Output is correct
10	Correct	65 ms	30024 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	8528 KB	Output is correct
2	Correct	2 ms	8528 KB	Output is correct
3	Correct	2 ms	8784 KB	Output is correct
4	Correct	58 ms	30024 KB	Output is correct
5	Correct	60 ms	30028 KB	Output is correct
6	Correct	58 ms	30024 KB	Output is correct
7	Correct	62 ms	30200 KB	Output is correct
8	Correct	59 ms	30220 KB	Output is correct
9	Correct	71 ms	30080 KB	Output is correct
10	Correct	65 ms	30024 KB	Output is correct
11	Correct	7 ms	9552 KB	Output is correct
12	Correct	65 ms	30324 KB	Output is correct
13	Correct	65 ms	30536 KB	Output is correct
14	Correct	61 ms	30536 KB	Output is correct
15	Correct	61 ms	30308 KB	Output is correct
16	Correct	74 ms	30536 KB	Output is correct
17	Correct	66 ms	30280 KB	Output is correct
18	Correct	82 ms	30280 KB	Output is correct
19	Correct	62 ms	30536 KB	Output is correct
20	Correct	60 ms	30512 KB	Output is correct