Submission #251697

#	Time	Username	Problem	Language	Result	Execution time	Memory
251697		LifeHappen__	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	367 ms	53884 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define forinc(a, b, c) for(int a=b, _c=c; a<=_c; ++a)
#define fordec(a, b, c) for(int a=b, _c=c; a>=_c; --a)
#define forv(a, b) for(auto &a : b)
#define rep(i, n) forinc(i, 1, n)
#define repv(i, n) forinc(i, 0, n - 1)

#define pb push_back
#define eb emplace_back
#define all(a) begin(a), end(a)
#define fi first
#define se second

const int N=1e5+5;
int n,m,st[N],en[N],pd[N][32],dep[N],id;
struct pack {int u,v,c;};
vector<int> ad[N];
vector<pack> que[N];
int f[N], g[N], it[N<<2], lz[N<<2];
void push(int i){
    if(lz[i]){
        int val=lz[i];
        lz[i<<1]+=val; lz[i<<1|1]+=val;
        it[i<<1]+=val; it[i<<1|1]+=val;
        lz[i]=0;
    }
}
void upd(int i,int l,int r,int u,int v,int val){
    if(v<l || u>r) return;
    if(u<=l && r<=v) {
        it[i]+=val; lz[i]+=val;
        return;
    }
    int mid=(l+r)>>1;
    push(i);
    upd(i<<1, l, mid, u, v, val); upd(i<<1|1, mid+1, r, u, v, val);
    it[i] = it[i<<1] + it[i<<1|1];
}
int get(int i,int l,int r,int u,int v){
    if(v<l || u>r) return 0;
    if(u<=l && r<=v) return it[i];
    int mid=(l+r)>>1;
    push(i);
    return get(i<<1, l, mid, u, v) + get(i<<1|1, mid+1, r, u, v);
}
void dfs(int u,int par=-1){
    rep(i,20) pd[u][i]=pd[pd[u][i-1]][i-1];
    st[u]=++id;
    forv(v,ad[u]) if(v!=par){
        dep[v]=dep[u]+1;
        pd[v][0]=u;
        dfs(v,u);
    }
    en[u]=id;
}
int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    int unx=dep[u]-dep[v];
    fordec(i,20,0) if(unx>>i&1) u=pd[u][i];
    if(u==v) return u;
    fordec(i,20,0) if(pd[u][i]!=pd[v][i]) u=pd[u][i], v=pd[v][i];
    return pd[u][0];
}
bool in(int u,int v){return st[u]<=st[v] && en[u]>=en[v];}
void dfs1(int u,int par){
    forv(v,ad[u]) if(v!=par) {
        dfs1(v,u);
        g[u]+=f[v];
    }
    forv(v,ad[u]) if(v!=par){
        upd(1,1,n,st[v],en[v],g[u]-f[v]);
    }
    f[u]=g[u];
    forv(v,que[u]){
        int x=v.u, y=v.v, c=v.c;
        int hx=get(1,1,n,st[x],st[x]);
        int hy=get(1,1,n,st[y],st[y]);
        int cur=hx+hy+g[x]+g[y]-g[u]+c;
        f[u]=max(f[u],cur);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    #define task "election"
    if(fopen(task".inp", "r")) freopen(task".inp", "r", stdin);
    cin>>n;
    rep(i,n-1){
        int u,v; cin>>u>>v;
        ad[u].pb(v); ad[v].pb(u);
    }
    dfs(1,0);
    cin>>m;
    forinc(i,1,m){
        int u,v,c; cin>>u>>v>>c;
        int p=lca(u,v);
        que[p].pb({u, v, c});
    }
    dfs1(1,0);
    cout<<f[1];
}

Compilation message (stderr)

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:91:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     if(fopen(task".inp", "r")) freopen(task".inp", "r", stdin);
                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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