Submission #153832

#	Time	Username	Problem	Language	Result	Execution time	Memory
153832		karma	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	364 ms	34936 KiB

election_campaign

#include<bits/stdc++.h>
#define pb      emplace_back

using namespace std;

const int N = int(2e5) + 7;
const int logN = 17;

int n, m, u, v, cur, res, fr[N], to[N], c[N], f[N], g[N];
int h[N], p[N][logN], Time = 0, in[N], out[N], t[N];
vector<int> q[N], a[N];

void BuildTree(int u, int par) {
     p[u][0] = par; in[u] = ++Time;
     for(int i = 1; i < logN; ++i) p[u][i] = p[p[u][i - 1]][i - 1];
     for(int v: a[u]) {
        if(v == par) continue;
        h[v] = h[u] + 1;
        BuildTree(v, u);
     }
     out[u] = Time;
}

int LCA(int u, int v) {
    if(h[u] < h[v]) swap(u, v);
    for(int i = logN - 1; i >= 0; --i)
        if(h[u] - (1 << i) >= h[v]) u = p[u][i];
    if(u == v) return u;
    for(int i = logN - 1; i >= 0; --i)
       if(p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
    return p[u][0];
}

void Update(int x, int val) {for(; x <= n; x += (x & -x)) t[x] += val;}
int Query(int x) {int res = 0; for(; x > 0; x -= (x & -x)) res += t[x]; return res;}

void GetAns(int u) {
     for(int v: a[u]) {
        if(v == p[u][0]) continue;
        GetAns(v); g[u] += f[v];
     }
     for(int v: a[u]) {
        if(v == p[u][0]) continue;
        Update(in[v], g[u] - f[v]);
        Update(out[v] + 1, f[v] - g[u]);
     }
     f[u] = g[u];
     for(int i: q[u]) {
        cur = g[fr[i]] + g[to[i]] - g[u] + Query(in[fr[i]]) + Query(in[to[i]]) + c[i];
        f[u] = max(f[u], cur);
     }
     res = max(res, f[u]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin >> n;
    for(int i = 1; i < n; ++i) {
        cin >> u >> v;
        a[u].pb(v), a[v].pb(u);
    }
    BuildTree(1, 1);
    cin >> m;
    for(int i = 0; i < m; ++i) {
        cin >> fr[i] >> to[i] >> c[i];
        q[LCA(fr[i], to[i])].pb(i);
    }
    res = 0;
    GetAns(1);
    cout << res;
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.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