Submission #1040270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040270		shezitt	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	161 ms	57620 KiB

election_campaign

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

#define int ll
#define fore(a, b, c) for(int a=b; a<c; ++a)
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define F first
#define S second
#define ii pair<int,int>
#define dbg(x) cerr << #x << ": " << x << endl
#define raya cerr << "=============" << endl

const int N = 2e5+5;
const int LG = 20;

struct fenwick {
    int n;
    vi t;
    fenwick(int n) : n(n) {
        t.assign(n+5, 0);
    }
    void add(int i, int x){
        for(; i<=n; i+=i&-i){
            t[i] += x;
        }
    }
    int query(int i){
        int r = 0;
        for(; i>0; i-=i&-i){
            r += t[i];
        }
        return r;
    }
} bit(N-5);

vi adj[N];
vector<array<int,3>> ways[N];
int dp[N][2];
int pa[N][LG];
int dep[N];
int timer;
int entro[N], salgo[N];

int n, m;

void dfs(int at, int ante=0){
    entro[at] = ++timer;
    pa[at][0] = ante;
    for(int u : adj[at]){
        if(u == ante) continue;
        dep[u] = dep[at] + 1;
        dfs(u, at);
    }
    salgo[at] = timer;
}

int jump(int a, int k){
    fore(i, 0, LG){
        if((k >> i) & 1){
            a = pa[a][i];
        }
    }
    return a;
}

int lca(int a, int b){
    if(dep[a] > dep[b]) swap(a, b);
    b = jump(b, dep[b] - dep[a]);
    if(a == b) return a;
    for(int i=LG-1; i>=0; --i){
        if(pa[a][i] != pa[b][i]){
            a = pa[a][i];
            b = pa[b][i];
        }
    }
    return pa[a][0];
}

int f(int at, int tomo){
    int &res = dp[at][tomo];
    if(res > -1) return res;
    res = 0;

    if(tomo == 0){
        int cur = 0;
        for(int u : adj[at]){
            if(u == pa[at][0]) continue;
            cur += max(f(u, 0), f(u, 1));
        }
        res = cur;
    }

    if(tomo == 1){
        int sintomar = f(at, 0);
        int mx = sintomar;
        for(auto [a, b, c] : ways[at]){
            int tmp = bit.query(entro[a]) + bit.query(entro[b]) + c;
            mx = max(mx, sintomar + tmp);
        }
        res = mx;  // tomando
        // es posible que sintomar = res, es decir que lo mejor es no tomar nada. 
        bit.add(entro[at], sintomar - res);
        bit.add(salgo[at]+1, res - sintomar);
    }

    return res;

}

signed main(){
    memset(dp, -1, sizeof dp);
    cin >> n;
    fore(i, 1, n){
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }    

    dfs(1);
    for(int i=1; i<LG; ++i){
        for(int j=1; j<=n; ++j){
            pa[j][i] = pa[pa[j][i-1]][i-1];
        }
    }

    cin >> m;
    fore(i, 0, m){
        int a, b, c;
        cin >> a >> b >> c;
        ways[lca(a, b)].pb({a, b, c});
    }

    int ans = max(f(1, 0), f(1, 1));
    
    cout << ans << endl;

}

Compilation message (stderr)

election_campaign.cpp: In function 'll f(ll, ll)':
election_campaign.cpp:102:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |         for(auto [a, b, c] : ways[at]){
      |                  ^

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