Submission #330272

#	Time	Username	Problem	Language	Result	Execution time	Memory
330272		BeanZ	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	340 ms	48256 KiB

election_campaign

// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 2e5 + 5;
const int lg = 18;
const int mod = 1e9 + 7;
const long long oo = 1e18;
const int lim = 1e6;
ll tin[N], tout[N], dp[N][19], f[N], dep[N];
ll timer = 0;
ll bit[N];
vector<ll> node[N];
struct viet{
    ll u, v, c;
};
vector<viet> Q[N];
void upd(ll u, ll v){
    ll res = 0;
    for (int i = u; i <= timer; i += i & -i){
        bit[i] += v;
    }
}
ll get(ll u){
    ll res = 0;
    for (int i = u; i > 0; i -= i & -i) res += bit[i];
    return res;
}
void dfs2(ll u, ll p){
    for (auto j : node[u]){
        if (j == p) continue;
        dfs2(j, u);
        upd(tin[u], f[j]);
        upd(tout[u], -f[j]);
    }
    for (auto j : Q[u]){
        f[u] = max(f[u], get(tin[j.u]) + get(tin[j.v]) - get(tin[u]) - get(tin[p]) + j.c);
    }
    f[u] = max(f[u], get(tin[u]) - get(tin[p]));
    upd(tin[u], -f[u]);
    upd(tout[u], f[u]);
}
void dfs(ll u, ll p){
    timer++;
    tin[u] = timer;
    for (int i = 1; i <= lg; i++) dp[u][i] = dp[dp[u][i - 1]][i - 1];
    for (auto j : node[u]){
        if (j == p) continue;
        dp[j][0] = u;
        dep[j] = dep[u] + 1;
        dfs(j, u);
    }
    timer++;
    tout[u] = timer;
}
ll LCA(ll u, ll v){
    if (dep[u] > dep[v]) swap(u, v);
    ll dis = dep[v] - dep[u];
    for (int i = lg; i >= 0; i--){
        if (dis & (1 << i)){
            v = dp[v][i];
        }
    }
    if (u == v) return u;
    for (int i = lg; i >= 0; i--){
        if (dp[u][i] != dp[v][i]){
            u = dp[u][i];
            v = dp[v][i];
        }
    }
    return dp[u][0];
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("A.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n;
    cin >> n;
    for (int i = 1; i < n; i++){
        ll u, v;
        cin >> u >> v;
        node[u].push_back(v);
        node[v].push_back(u);
    }
    dfs(1, 1);
    ll m;
    cin >> m;
    for (int i = 1; i <= m; i++){
        ll u, v, c;
        cin >> u >> v >> c;
        ll lca = LCA(u, v);
        Q[lca].push_back({u, v, c});
    }
    dfs2(1, 0);
    cout << f[1];
}
/*
*/

Compilation message (stderr)

election_campaign.cpp: In function 'void upd(long long int, long long int)':
election_campaign.cpp:20:8: warning: unused variable 'res' [-Wunused-variable]
   20 |     ll res = 0;
      |        ^~~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   78 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   79 |         freopen("test.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