Submission #252215

#	Time	Username	Problem	Language	Result	Execution time	Memory
252215		someone	Election Campaign (JOI15_election_campaign)	C++14	0 / 100	223 ms	39672 KiB

election_campaign

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

struct Way {
    int a, b, cost;
};

const int M = 1 << 17, N = 2*M;

vector<int> adj[M];
vector<Way> way[M];
int n, m, l = M, deb[M], fin[M], sum[M], a[N], par[N][19];

bool isAnc(int a, int b) {
    if(a == -1) return true;
    return deb[a] <= deb[b] && fin[b] <= fin[a];
}

void DFS(int i, int pre) {
    deb[i] = l++;
    par[i][0] = pre;
    for(int j : adj[i])
        if(j != pre)
            DFS(j, i);
    fin[i] = l++;
}

int LCA(int a, int b) {
    if(isAnc(a, b))
        return a;
    if(isAnc(b, a))
        return b;
    int c = a;
    for(int i = 18; i > -1; i--)
        if(!isAnc(par[c][i], b))
            c = par[c][i];
    return par[c][0];
}

int getSum(int i)  {
    int t = 0;
    while(i > 0) {
        if(i % 2 == 1)
            t += a[i-1];
        i /= 2;
    }
    return t;
}

void insert(int i, int val) {
    while(i > 0) {
        a[i] += val;
        i /= 2;
    }
}

int getWay(int a, int b, int lca) {
    return getSum(deb[a]+1) + getSum(deb[b]+1) - getSum(deb[lca]) - getSum(deb[lca]+1);
}

int get(int i) {
    for(int j : adj[i])
        if(j != par[i][0])
            sum[i] += get(j);
    int val = 0;
    for(Way w : way[i])
        val = max(val, w.cost - getWay(w.a, w.b, i));
    sum[i] += val;
    insert(deb[i], val);
    insert(fin[i], -val);
    return sum[i];
}

signed main() {
    /*
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    */
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    for(int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    DFS(0, -1);
    for(int i = 0; i < 18; i++)
        for(int j = 0; j < n; j++)
            if(par[j][i] == -1)
                par[j][i+1] = -1;
            else
                par[j][i+1] = par[par[j][i]][i];
    
    cin >> m;
    for(int i = 0; i < m; i++) {
        int a, b, cost;
        cin >> a >> b >> cost;
        a--, b--;
        int c = LCA(a, b);
        way[c].push_back({a, b, cost});
    }
    cout << get(0);
}

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