Submission #972572

#	Time	Username	Problem	Language	Result	Execution time	Memory
972572		yeediot	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	270 ms	45600 KiB

election_campaign

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
struct line{
    int a,b;
    int operator()(const int x)const{
        return a*x+b;
    }
};
bool check(line l1,line l2,line l3){
    return (l3.b-l2.b)*(l1.a-l2.a)<=(l2.b-l1.b)*(l2.a-l3.a);
}
const int mxn=1e5+5;
vector<int>adj[mxn];
int cnt[mxn],t[mxn],in[mxn],out[mxn],pa[mxn],tmr,jump[20][mxn],dep[mxn];
void dfs(int v,int p){
    cnt[v]=1;
    pa[v]=p;
    jump[0][v]=p;
    dep[v]=dep[p]+1;
    for(auto u:adj[v]){
        if(u==p)
            continue;
        dfs(u,v);
        cnt[v]+=cnt[u];
    }
}
void hld(int v,int top,int p){
    in[v]=++tmr;
    t[v]=top;
    int mx=-1;
    for(auto u:adj[v]){
        if(u==p)
            continue;
        if(mx==-1 or cnt[u]>cnt[mx]){
            mx=u;
        }
    }
    if(mx!=-1){
        hld(mx,top,v);
    }
    for(auto u:adj[v]){
        if(u==p or u==mx)
            continue;
        hld(u,u,v);
    }
    out[v]=tmr;
}
int lca(int a,int b){
    if(dep[a]<dep[b]){
        swap(a,b);
    }
    int dif=dep[a]-dep[b];
    for(int i=0;i<20;i++){
        if(dif>>i&1){
            a=jump[i][a];
        }
    }
    if(a==b){
        return a;
    }
    for(int i=19;i>=0;i--){
        if(jump[i][a]!=jump[i][b]){
            a=jump[i][a];
            b=jump[i][b];
        }
    }
    return jump[0][a];
}
struct BIT{
    int bit[mxn];
    void init(){
        for(int i=0;i<mxn;i++){
            bit[i]=0;
        }
    }
    void modify(int p,int v){
        for(;p<mxn;p+=p&-p){
            bit[p]+=v;;
        }
    }
    int query(int p){
        int res=0;
        for(;p;p-=p&-p){
            res+=bit[p];
        }
        return res;
    }
    int query(int l,int r){
        return query(r)-query(l-1);
    }
}bt;
int path(int a,int b){
    int res=0;
    int ta=t[a],tb=t[b];
    while(ta!=tb){
        if(dep[ta]<dep[tb]){
            swap(a,b);
            swap(ta,tb);
        }
        res+=bt.query(in[ta],in[a]);
        a=pa[ta],ta=t[a];
    }
    if(in[a]>in[b])
        swap(a,b);
    res+=bt.query(in[a],in[b]);
    return res;
}
int dp[mxn];
vector<tuple<int,int,int,int>>ck[mxn];
void calc(int v,int p){
    int sum=0;
    for(auto u:adj[v]){
        if(u==p)
            continue;
        calc(u,v);
        sum+=dp[u];
    }
    dp[v]=sum;
    for(auto [x,a,b,c]:ck[v]){
        dp[v]=max(dp[v],sum+path(a,b)+c);
    }
    bt.modify(in[v],sum-dp[v]);
}
signed main(){
    setio();
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dfs(1,1);
    hld(1,1,1);
    bt.init();
    for(int i=1;i<20;i++){
        for(int j=1;j<=n;j++){
            jump[i][j]=jump[i-1][jump[i-1][j]];
        }
    }
    int q;
    cin>>q;
    for(int i=1;i<=q;i++){
        int a,b,c;
        cin>>a>>b>>c;
        int x=lca(a,b);
        ck[x].pb({x,a,b,c});
    }
    calc(1,1);
    cout<<dp[1]<<'\n';
}
 /*
 input:
 
 */















 

Compilation message (stderr)

election_campaign.cpp: In function 'void setIO(std::string)':
election_campaign.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen((s + ".out").c_str(), "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