이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
const int K = 17;
bool maximize(auto &a, auto b) {
if(a >= b) return true;
a = b;
return false;
}
int n, m, numDFS;
int dep[N], P[N][K], in[N], out[N];
ll dp[N], f[N], bit[N];
vector<int> g[N];
vector<tuple<int, int, int>> plans[N];
void update(int i, ll val) {
for(; i <= n; i += i & -i) bit[i] += val;
}
void update(int l, int r, ll val) {
update(l, val);
update(r + 1, -val);
}
ll get(int i) {
ll res = 0;
for(; i; i -= i & -i) res += bit[i];
return res;
}
void euler_tour(int u, int p = 0) {
in[u] = ++numDFS;
dep[u] = dep[p] + 1;
P[u][0] = p;
for(int i = 1; i < K; ++i) P[u][i] = P[P[u][i - 1]][i - 1];
for(int v : g[u]) if(v != p) {
euler_tour(v, u);
}
out[u] = numDFS;
}
int lca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
for(int i = K - 1; i >= 0; --i) if(dep[P[u][i]] >= dep[v]) u = P[u][i];
for(int i = K - 1; i >= 0; --i) if(P[u][i] != P[v][i]) u = P[u][i], v = P[v][i];
return u == v ? u : P[u][0];
}
void dfs(int u, int p = 0) {
for(int v : g[u]) if(v != p) dfs(v, u);
for(auto [v1, v2, c] : plans[u]) {
maximize(dp[u], f[u] - get(in[v1]) - get(in[v2]) + c);
}
maximize(dp[u], f[u]);
update(in[u], out[u], dp[u] - f[u]);
f[p] += dp[u];
}
void solve() {
cin >> n;
for(int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
euler_tour(1);
cin >> m;
for(int i = 1, u, v, c; i <= m; ++i) {
cin >> u >> v >> c;
int p = lca(u, v);
plans[p].emplace_back(u, v, c);
}
dfs(1);
cout << dp[1] << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int test = 1;
// cin >> test;
while(test--) solve();
return 0;
}
// https://oj.uz/problem/view/JOI15_election_campaign
컴파일 시 표준 에러 (stderr) 메시지
election_campaign.cpp:7:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
7 | bool maximize(auto &a, auto b) {
| ^~~~
election_campaign.cpp:7:24: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
7 | bool maximize(auto &a, auto b) {
| ^~~~
election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:54:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
54 | for(auto [v1, v2, c] : plans[u]) {
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |