Submission #77868

#	Time	Username	Problem	Language	Result	Execution time	Memory
77868		thebes	Election Campaign (JOI15_election_campaign)	C++14	30 / 100	1084 ms	109352 KiB

election_campaign

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,ssse3,sse3,sse4,popcnt,avx,mmx,abm,tune=native")
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int MN = 1e5+5;
int dp[MN][2], sp[MN][20][2], anc[MN][20], N, M, i, x, y, w, dep[MN];
struct qur{int x, y, w;}path[MN];
vector<int> adj[MN], id[MN];
vector<pair<int,int>> bld[MN];
void init(int n,int p,int d){
    dep[n]=d; anc[n][0]=p;
    for(auto v : adj[n])
        if(v != p) init(v, n, d+1);
}
inline int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=19;i>=0;i--){
        if(dep[x]-dep[y]>=(1<<i))
            x = anc[x][i];
    }
    if(x == y) return x;
    for(int i=19;i>=0;i--){
        if(anc[x][i]!=anc[y][i]){
            x = anc[x][i];
            y = anc[y][i];
        }
    }
    return anc[x][0];
}
inline int qu(int x,int y,int id){
    int res = 0;
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=19;i>=0;i--){
        if(dep[x]-dep[y]>=(1<<i))
            res += sp[x][i][id], x = anc[x][i];
    }
    if(x == y) return res+dp[x][id];
    for(int i=19;i>=0;i--){
        if(anc[x][i]!=anc[y][i]){
            res += sp[x][i][id]+sp[y][i][id];
            x = anc[x][i], y = anc[y][i];
        }
    }
    return res+sp[x][0][id]+sp[y][0][id]+dp[anc[x][0]][id];
}
inline int adv(int n,int d){
    for(int i=19;i>=0;i--){
        if((1<<i)<=d)
            n=anc[n][i],d-=(1<<i);
    }
    return n;
}
void solve(int n,int p){
    int idk;
    for(int i=1;i<20;i++){
        idk = adv(n, (1<<i)-1);
        bld[idk].push_back({n,i});
        if(!idk) break;
    }
    for(auto v : adj[n]){
        if(v == p) continue;
        solve(v, n);
        dp[n][1] += dp[v][0];
    }
    dp[n][0]=dp[n][1];
    for(auto i : id[n]){
        int x = path[i].x, y = path[i].y, w = path[i].w;
        dp[n][0]=max(dp[n][0],qu(x,y,1)-qu(x,y,0)+dp[n][0]+w);
    }
    sp[n][0][0]=dp[n][0];
    sp[n][0][1]=dp[n][1];
    sort(bld[n].begin(),bld[n].end(),[](pair<int,int>i,pair<int,int>j){return dep[i.first]<dep[j.first];});
    for(auto v : bld[n]){
        for(int i=0;i<2;i++)
            sp[v.first][v.second][i]=sp[v.first][v.second-1][i]+sp[anc[v.first][v.second-1]][v.second-1][i];
    }
}
signed main(){
    for(scanf("%lld",&N),i=1;i<N;i++){
        scanf("%lld%lld",&x,&y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    init(1, 0, 1);
    for(int j=1;j<20;j++){
        for(i=1;i<=N;i++)
            anc[i][j]=anc[anc[i][j-1]][j-1];
    }
    for(scanf("%lld",&M),i=1;i<=M;i++){
        scanf("%lld%lld%lld",&x,&y,&w);
        path[i] = {x, y, w};
        id[lca(x,y)].push_back(i);
    }
    solve(1, 0);
    printf("%lld\n",dp[1][0]);
    return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:82:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%lld",&N),i=1;i<N;i++){
         ~~~~~~~~~~~~~~~~^~~~
election_campaign.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~~~~
election_campaign.cpp:92:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%lld",&M),i=1;i<=M;i++){
         ~~~~~~~~~~~~~~~~^~~~
election_campaign.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&x,&y,&w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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