Submission #157688

#	Time	Username	Problem	Language	Result	Execution time	Memory
157688		nvmdava	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	240 ms	32212 KiB

election_campaign

#include <bits/stdc++.h>
#define N 100005
using namespace std;
#define ll long long
#define ff first
#define ss second

ll bit[N];

ll get(int v){
    ll s = 0;
    while(v){
        s += bit[v];
        v -= v & -v;
    }
    return s;
}

void update(int x, ll v){
    while(x < N){
        bit[x] += v;
        x += x & -x;
    }
}
 
vector<int> adj[N];
 
int in[N], out[N], p[N][20];
int d[N];
 
int n;
int cnt;
 
void dfs2(int v, int par){
    in[v] = ++cnt;
    
    d[v] = d[par] + 1;
    p[v][0] = par;
    
    for(int i = 0; p[v][i] != 0; i++){
        p[v][i + 1] = p[p[v][i]][i];    
    }
    
    for(int& x : adj[v]){
        if(x == par) continue;
        dfs2(x, v);
    }
    
    out[v] = cnt;
}
 
int find(int v, int u){
    if(d[v] < d[u]) swap(v, u);
    
    for(int i = 0; d[v] - d[u]; i++)
        if((d[v] - d[u]) & (1 << i))
            v = p[v][i];    
    
    if(v == u) return v;
    for(int i = 18; i >= 0; i--){
        if(p[v][i] != p[u][i]){
            v = p[v][i];
            u = p[u][i];
        }
    }
    return p[v][0];
}
 
vector<pair<pair<int, int>, int> > obj[N];
 
ll is1[N], is0[N];
 
void dfs(int v, int p){
    ll res = 0;
    
    for(int& x : adj[v]){
        if(x == p) continue;
        dfs(x, v);
        res += is1[x];
    }
    
    is1[v] = is0[v] = res;
    
    
    for(auto& x : obj[v])
        is1[v] = max(is1[v], res + x.ss + get(in[x.ff.ff]) + get(in[x.ff.ss]));
    

    update(in[v], res - is1[v]);
    update(out[v] + 1, is1[v] - res);
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n;
    
    for(int v, u, i = 1; i < n; i++){
        cin>>v>>u;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }
    
    dfs2(1, 0);
    
    cin>>n;
    while(n--){
        int a, b, c;
        cin>>a>>b>>c;
        obj[find(a, b)].push_back({{a, b}, c});
    }
    
    dfs(1, 0);
    
    cout<<is1[1];
}

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