Submission #1120535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120535		InvMOD	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	285 ms	36100 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define dbg(x) "[" #x " = " << (x) << "]"
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 1e5+5;
const int lg = 20;

int n, q, timerDFS, curChain;

int id[N], head[N], tin[N], tour[N], parLCA[lg][N], h[N], sz[N], par[N];

ll dp[N], sumDP[N], bit[2][N];

vector<int> adj[N];

vector<array<int, 2>> Query[N];

vector<array<int, 3>> QueryPair[N];

void update(int id, int p, ll val){
    for(; p <= timerDFS; p += p&-p){
        bit[id][p] += val;
    }
    return;
}

ll get_range(int id, int l, int r){
    ll res = 0;
    for(r; r > 0; r -= r&-r){
        res += bit[id][r];
    }
    for(--l; l > 0; l -= l&-l){
        res -= bit[id][l];
    }
    return res;
}

void dfs(int x = 1, int p = -1){
    sz[x] = 1;
    for(int v : adj[x])if(v != p){
        parLCA[0][v] = x;
        for(int i = 1; i < lg; i++){
            parLCA[i][v] = parLCA[i-1][parLCA[i-1][v]];
        }
        par[v] = x, h[v] = h[x] + 1;

        dfs(v, x);
        sz[x] += sz[v];
    }
    return;
}

void decompose(int x = 1, int p = -1){
    if(!head[curChain]) head[curChain] = x;

    id[x] = curChain;
    tour[tin[x] = ++timerDFS] = x;

    int nxt = 0;
    for(int v : adj[x]) if(v != p && sz[v] > sz[nxt]) nxt = v;

    if(nxt) decompose(nxt, x);

    for(int v : adj[x]){
        if(v == p || v == nxt) continue;
        ++curChain;
        decompose(v, x);
    }
    return;
}

int get_LCA(int u, int v){
    while(id[u] != id[v]){
        if(id[u] > id[v]) u = par[head[id[u]]];
        else{
            v = par[head[id[v]]];
        }
    }
    return h[u] < h[v] ? u : v;
}

void update_Node(int id, int x, ll val){
    update(id, tin[x], val);
}

ll query_Path(int idx, int u, int v){
    int lca = get_LCA(u, v);

    ll res = 0;
    while(id[u] != id[lca]){
        res = res + get_range(idx, tin[head[id[u]]], tin[u]);
        u = par[head[id[u]]];
    }

    while(id[v] != id[lca]){
        res = res + get_range(idx, tin[head[id[v]]], tin[v]);
        v = par[head[id[v]]];
    }
    if(h[u] > h[v]) swap(u, v);
    res = res + get_range(idx, tin[u], tin[v]);
    return res;
}

int binlift(int u, int k){
    if(k < 0) return u;
    for(int i = 0; i < lg; i++){
        if(k >> i & 1){
            u = parLCA[i][u];
        }
    }
    return u;
}

ll compute(int u, int v){
    if(h[u] > h[v]) swap(u, v);

    int parV = binlift(v, h[v] - h[u] - 1);
    return query_Path(0, u, v) - query_Path(1, parV, v);
}

// [0]: sumDP of x
// [1]: DP of x

void proc_dp(int x = 1, int p = -1){
    for(int v : adj[x])if(v != p){
        proc_dp(v, x);
        sumDP[x] += dp[v];
    }

    for(array<int,2> arr : Query[x]){
        int v = arr[0], cost = arr[1];

        ll curDP = sumDP[x] + compute(x, v) + (1ll * cost);
        //cout << dbg(compute(x, v)) <<"\n";
        dp[x] = max(dp[x], curDP);
    }

    for(array<int,3> arr : QueryPair[x]){
        int a = arr[0], b = arr[1], cost = arr[2];

        ll curDP = sumDP[x] + compute(x, a) + compute(x, b) + (1ll * cost);
        //cout << dbg(compute(x, a)) << dbg(compute(x, b)) <<"\n";
        dp[x] = max(dp[x], curDP);
    }

    //cout << dbg(x) << dbg(sumDP[x]) << dbg(dp[x]) <<"\n";
    dp[x] = max(dp[x], sumDP[x]);

    update_Node(0, x, sumDP[x]);
    update_Node(1, x, dp[x]);
    return;
}

void solve()
{
    cin >> n;
    FOR(i, 1, n-1){
        int u,v; cin >> u >> v;
        adj[u].pb(v), adj[v].pb(u);
    }

    dfs(), decompose();


    cin >> q;
    FOR(i, 1, q){
        int a,b,cost;
        cin >> a >> b >> cost;
        int lca = get_LCA(a, b);

        if(lca == a || lca == b){
            Query[lca].push_back({lca ^ a ^ b, cost});
        }
        else{
            QueryPair[lca].push_back({a, b, cost});
        }
    }

    proc_dp();
    cout << *max_element(dp+1, dp+1+n) <<"\n";

    return;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'll get_range(int, int, int)':
election_campaign.cpp:47:9: warning: statement has no effect [-Wunused-value]
   47 |     for(r; r > 0; r -= r&-r){
      |         ^
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:211:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  211 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:212:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |         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