Submission #1293107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293107		trandangquang	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	215 ms	34796 KiB

election_campaign

#include<bits/stdc++.h>
using namespace std;

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define _ << " " <<

template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int N=101010;
const int LG=17;

int n,np;
int pa[N],pb[N],pc[N];
vector<int> adj[N];
void input(){
    cin>>n;
    rep(i,n-1){
        int x,y; cin>>x>>y;
        adj[x].eb(y); adj[y].eb(x);
    }
    cin>>np;
    foru(i,1,np){
        cin>>pa[i]>>pb[i]>>pc[i];
    }
}

int sz[N],tin[N],tout[N],up[N][LG+1],h[N],tim;
void preDfs(int u, int p=-1){
    sz[u]=1;
    for(int v:adj[u]) if(v!=p){
        up[v][0]=u;
        foru(i,1,LG) up[v][i]=up[up[v][i-1]][i-1];
        h[v]=h[u]+1;
        preDfs(v,u);
        sz[u]+=sz[v];
    }
}
int lca(int u, int v){
    if(h[u]<h[v]) swap(u,v);
    int df=h[u]-h[v];
    foru(i,0,LG) if(bit(df,i)) u=up[u][i];
    if(u==v) return u;
    ford(i,LG,0) if(up[u][i]!=up[v][i]) u=up[u][i],v=up[v][i];
    return up[u][0];
}
bool chkSubtree(int root, int u){
    return tin[root]<=tin[u] && tout[u]<=tout[root];
}

int head[N],idCh[N],bigC[N],curCh=1;
void dfsHld(int u, int p=-1){
    if(!head[curCh]){
        head[curCh]=u;
    }
    tin[u]=++tim;
    idCh[u]=curCh;

    bigC[u]=-1;
    for(int v:adj[u]) if(v!=p) if(bigC[u]==-1||sz[bigC[u]]<sz[v]) bigC[u]=v;

    if(bigC[u]!=-1) dfsHld(bigC[u],u);
    for(int v:adj[u]) if(v!=p && v!=bigC[u]){
        ++curCh;
        dfsHld(v,u);
    }
    tout[u]=tim;
}

struct SegmentTree{
    int st[N<<2];
    void upd(int x, int val){
        int id=1, l=1, r=n;
        while(l<r){
            st[id]+=val;
            int mid=(l+r)>>1;
            if(x<=mid){id=id<<1; r=mid;}
            else{id=id<<1|1; l=mid+1;}
        }
        st[id]+=val;
    }
    int get(int u, int v, int id=1, int l=1, int r=n){
        if(u>r||v<l) return 0;
        if(u<=l&&r<=v) return st[id];
        int mid=(l+r)>>1;
        return get(u,v,id<<1,l,mid)+get(u,v,id<<1|1,mid+1,r);
    }
} smt;

vector<int> hihi[N];
void prepare(){
    foru(i,1,np){
        int l=lca(pa[i],pb[i]);
        hihi[l].eb(i);
    }
}

int dp[N],sumDp[N];
void dfsDP(int u, int p=-1){
    for(int v:adj[u]) if(v!=p){
        dfsDP(v,u);
        sumDp[u]+=dp[v];
    }

    dp[u]=sumDp[u];
//    if(u==1)cout<<sumDp[u]<<'\n';
    for(int i:hihi[u]){
        int x=pa[i], y=pb[i];
        if(tin[x]>tin[y]) swap(x,y);

        if(chkSubtree(x,y)){
            int tot=pc[i]+sumDp[y];
            while(idCh[x]!=idCh[y]){
                tot+=smt.get(tin[head[idCh[y]]]+1,tin[y]);
                tot+=sumDp[up[head[idCh[y]]][0]]-dp[head[idCh[y]]];
                y=up[head[idCh[y]]][0];
            }
//            if(u==1)cout<<tot _ tin[x]+1 _ tin[y]<<'\n';
            tot+=smt.get(tin[x]+1,tin[y]);
            maxi(dp[u],tot);
        } else{
            int nx=x, ny=y;
            ford(j,LG,0){
                if(h[up[nx][j]]>h[u]) nx=up[nx][j];
                if(h[up[ny][j]]>h[u]) ny=up[ny][j];
            }

            int tot=pc[i]+sumDp[x]+sumDp[y];
            while(idCh[nx]!=idCh[x]){
                tot+=smt.get(tin[head[idCh[x]]]+1,tin[x]);
                tot+=sumDp[up[head[idCh[x]]][0]]-dp[head[idCh[x]]];
                x=up[head[idCh[x]]][0];
            }
            tot+=smt.get(tin[nx]+1,tin[x]);

            while(idCh[ny]!=idCh[y]){
                tot+=smt.get(tin[head[idCh[y]]]+1,tin[y]);
                tot+=sumDp[up[head[idCh[y]]][0]]-dp[head[idCh[y]]];
                y=up[head[idCh[y]]][0];
            }
            tot+=smt.get(tin[ny]+1,tin[y]);

            tot+=sumDp[u]-dp[nx]-dp[ny];

            maxi(dp[u],tot);
        }
    }

    if(p!=-1){
//            cout<<tin[bigC[p]] _ dp[u] _ u<<'\n';
        if(bigC[p]!=u) smt.upd(tin[bigC[p]],dp[u]);
    }

//    cout<<dp[u] _ u<<'\n';
}

void solve(){
    input();
    preDfs(1);
    dfsHld(1);
    prepare();
    dfsDP(1);

    cout<<dp[1]<<'\n';
}

int32_t main(){
    #define task "test"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    int tc=1; //cin>>tc;
    rep(i,tc){
        solve();
    }
}

Compilation message (stderr)

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