Submission #684690

#	Time	Username	Problem	Language	Result	Execution time	Memory
684690		Ronin13	Election Campaign (JOI15_election_campaign)	C++14	30 / 100	427 ms	35424 KiB

election_campaign

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 1e5 + 1;
int in[nmax];
vector <vector <int> > g(nmax);
vector <int> sz(nmax);

vector <ll> t(4 * nmax);

void update(int v, int l, int r, int pos, ll val){
    if(l > pos || r < pos) return;
    if(l == r){
        t[v] = val;
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, val);
    update(2 * v + 1, m + 1, r, pos, val);
    t[v] = t[2 * v] + t[2 * v + 1];
}

int get(int v, int l, int r, int st, int fin){
    if(l > fin || r < st) return 0;
    if(l >= st && r <= fin) return t[v];
    int m = (l + r) / 2;
    return get(2 * v, l, m, st, fin) + get(2 * v + 1, m + 1, r, st, fin);
}

int lead[nmax];
int a[nmax][22];

void dfs(int v, int e = -1){
    sz[v] = 1;
    a[v][0] = e;
    for(int j = 1; j <= 20; j++){
        if(a[v][j - 1] != -1) a[v][j] = a[a[v][j - 1]][j - 1];
        else a[v][j] = -1;
    }
    for(int to : g[v]){
        if(to == e) continue;
        dfs(to, v);
        sz[v] += sz[to];
    }
    for(int j = 1; j < g[v].size(); j++){
        int x = g[v][j];
        if(sz[x] * 2 >= sz[v]) {
            swap(g[v][j], g[v][0]);
        }
    }
}
int timer = 1;
int out[nmax];
int outtimer = 1;
void DFS(int v, int l, int e = -1){
    in[v] = timer++;
    lead[v] = l;
    for(int to : g[v]){
        if(to == e) continue;
        if(sz[to] * 2 >= sz[v]) DFS(to, l, v);
        else DFS(to, to, v);
    }
    out[v] = outtimer++;
}

bool is_ancestor(int a, int b){
    return in[a] < in[b] && out[a] > out[b];
}

int lca(int u, int v){
    if(is_ancestor(u, v)) return u;
    if(is_ancestor(v, u)) return v;
    for(int j =20; j >= 0; j--){
        if(a[v][j] == -1) continue;
        if(is_ancestor(a[v][j], u)) continue;
        v = a[v][j];
    }
    return a[v][0];
}
int n;
ll sum(int A, int B){
    ll ans = 0;
    while(lead[A] != lead[B]){
        int x = lead[A];
        ans += get(1, 1, n, in[x], in[A]);
        A = a[x][0];
    }
    ans += get(1, 1, n, in[B], in[A]);
    return ans;
}

ll dp[nmax];

vector <vector <pair<ll, pii> > > vec(nmax);

void DP_DFS(int v, int e = -1){
    for(int to : g[v]){
        if(to == e) continue;
        DP_DFS(to, v);
    }
    ll s = 0;
    for(int to : g[v])
        if(to != e) s += dp[to];
    dp[v] = s;
    for(auto ro : vec[v]){
        int x = ro.s.f, y = ro.s.s;
        ll val = ro.f;
        dp[v] = max(dp[v], sum(x, v) + sum(y, v) + s + val);
    }
    update(1, 1, n, in[v], s - dp[v]);
}

int main(){
    //ios_base::sync_with_stdio(false); cin.tie(0);
    cin >>n;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1);
    DFS(1, 1);

    int m; cin >> m;
   //cout << lca(2, 6) << "\n";
    for(int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        ll c; cin >> c;
        ll x = lca(u, v);
    //    cout << x << ' ';
        vec[x].pb({c, {u, v}});
    }

    DP_DFS(1);

    cout << dp[1];
    return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int j = 1; j < g[v].size(); j++){
      |                    ~~^~~~~~~~~~~~~

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