Submission #1285174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285174		thanhlhp	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	143 ms	41648 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define iii pair<int, ii>
#define fi first
#define se second
#define inf 10000000000000000
const int N = 2e5 + 5;
int n, m, h[N], up[N][20], f[N], in[N], out[N], bit1[N], bit2[N], cnt;
vector<int> g[N];
struct yc {
    int u, v, c;
};
vector<yc> qr[N];

void update1(int pos, int val) {
    for(pos;pos <= 2*n; pos += pos&(-pos)) bit1[pos] += val;
}
int get1(int pos) {
    int res = 0;
    for(pos;pos>0;pos -= pos&(-pos)) res += bit1[pos];
    return res;
}
int pathf(int u, int v, int l) {
    return get1(in[u]) + get1(in[v]) - 2*(get1(in[l])) + get1(in[l])-get1(in[l]-1);
}
void update2(int pos, int val) {
    for(pos;pos <= 2*n; pos += pos&(-pos)) bit2[pos] += val;
}
int get2(int pos) {
    int res = 0;
    for(pos;pos>0;pos -= pos&(-pos)) res += bit2[pos];
    return res;
}
int pathsum(int u, int v, int l) {
    return get2(in[u]) + get2(in[v]) - 2*(get2(in[l])) + get2(in[l])-get2(in[l]-1);
}
void build(int u, int par) {
    in[u] = ++cnt;
    for(int v : g[u]) {
        if(v == par) continue;
        h[v] = h[u] + 1;
        up[v][0] = u;
        for(int j = 1; j <= 19; j++) up[v][j] = up[up[v][j-1]][j-1];
        build(v,u);
    }
    out[u] = ++cnt;
}
int lca(int u, int v) {
    if(h[u] > h[v]) swap(u,v);
    int dis = h[v] - h[u];
    for(int j = 0; j <= 19; j++) {
        if(dis&(1<<j)) v = up[v][j];
    }
    if(u == v) return u;
    int k = __lg(h[u]);
    for(int j = k; j >= 0; j--) {
        if(up[v][j] != up[u][j]) {
            v = up[v][j];
            u = up[u][j];
        }
    }
    return up[u][0];
}
void dfs(int u, int par) {
    int sum = 0;
    for(int v : g[u]) {
        if(v == par) continue;
        dfs(v,u);
        sum += f[v];
    }
    f[u] = sum;
    update2(in[u],sum);
    update2(out[u],-sum);
    for(auto it : qr[u]) {
        int l = it.u, r = it.v, c = it.c;
//        if(u == 1) {
//            cout << "* " << l << ' ' << r << '\n';
//            cout << pathsum(l,r,u) << '\n';
//            cout << pathf(l,r,u) << '\n';
//        }
        f[u] = max(f[u],pathsum(l,r,u)-pathf(l,r,u) + c) ;
    }
    update1(in[u],f[u]);
    update1(out[u],-f[u]);
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen("main.inp","r")) {
        freopen("main.inp", "r", stdin);
        freopen("main.out", "w", stdout);
    }
    cin >> n;
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    build(1,1);
    cin >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        int l = lca(u,v);
        qr[l].push_back({u,v,c});
        //cout << u << ' ' << v << ' ' << l << ' ' << c << '\n';
    }
    dfs(1,1);
    cout << f[1];
    //for(int i = 1; i <= n; i++) cout << f[i] << '\n';
    return 0;
}

Compilation message (stderr)

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