Submission #78188

#	Time	Username	Problem	Language	Result	Execution time	Memory
78188		MladenP	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	251 ms	28132 KiB

election_campaign

#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 100010
#define MAXL 20
struct query{
    int A, B, C;
} q;
vector<query> qs[MAXN];
vector<int> adj[MAXN];
int N, siz[MAXN], idx[MAXN], seg[4*MAXN], anc[MAXN][MAXL], timer, idxx, in[MAXN], out[MAXN], dp[MAXN], dp1[MAXN];
int dfsLCA(int node, int prev) {
    idx[node] = ++timer; in[node] = ++idxx;
    anc[node][0] = prev; siz[node] = 1;
    for(auto x : adj[node]) {
        if(x != prev) {
            siz[node] += dfsLCA(x, node);
        }
    }
    out[node] = ++idxx;
    return siz[node];
}
void init() {
    dfsLCA(1, 1);
    for(int d = 1; d < MAXL; d++) {
        for(int i = 1; i <= N; i++) {
            anc[i][d] = anc[anc[i][d-1]][d-1];
        }
    }
}
bool inSubtree(int x, int y) {
    return (in[y] <= in[x] && out[x] <= out[y]);
}
int LCA(int x, int y) {
    if(inSubtree(x, y)) return y;
    if(inSubtree(y, x)) return x;
    for(int d = MAXL-1; d >= 0; d--) {
        if(!inSubtree(y, anc[x][d])) x = anc[x][d];
    }
    return anc[x][0];
}
int query(int node1, int l, int r, int idx) {
    if(l == r && l == idx) return seg[node1];
    if(r < l || idx < l || r < idx) return 0;
    return seg[node1] + query(2*node1, l, mid, idx) + query(2*node1+1, mid+1, r, idx);
}
int update(int node1, int l, int r, int L, int R, int val) {
    if(l > r || L > r || l > R || L > R) return 0;
    if(L <= l && r <= R) {
        return seg[node1] += val;
    }
    update(2*node1, l, mid, L, R, val); update(2*node1+1, mid+1, r, L, R, val);
}
int DFS(int node, int prev) {
    for(auto x : adj[node]) {
        if(x != prev) dp1[node] += DFS(x, node);
    }
    dp[node] = dp1[node];
    for(auto q : qs[node]) {
        dp[node] = max(dp[node], q.C + query(1, 1, N, idx[q.A]) + query(1, 1, N, idx[q.B]) + dp1[node]);
    }
    update(1, 1, N, idx[node], idx[node]+siz[node]-1, dp1[node]-dp[node]);
    return dp[node];
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> N;
    for(int i = 1; i < N; i++) {
        int x, y; cin >> x >> y;
        adj[x].pb(y); adj[y].pb(x);
    }
    init();
    int Q; cin >> Q;
    for(int i = 1; i <= Q; i++) {
        cin >> q.A >> q.B >> q.C;
        qs[LCA(q.A, q.B)].pb(q);
    }
    DFS(1, 1);
    cout << dp[1] << endl;
    return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'int update(int, int, int, int, int, int)':
election_campaign.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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