Submission #1138079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138079		imarn	Paths (RMI21_paths)	C++20	68 / 100	1096 ms	32168 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define t3 tuple<int,int,int>
using namespace std;
const int mxn=1e5+5;
vector<pair<int,ll>>g[mxn];
int rt=-1;
ll ans=0;
ll rs1=-1,rs2=-1;
ll dp[mxn][2]{0};
ll add[mxn]{0};
void dfs(int u,int p){
    dp[u][0]=dp[u][1]=0;
    for(auto [v,w]:g[u]){
        if(v==p)continue;
        dfs(v,u);
        ll t=dp[v][0]+w;
        if(t>dp[u][0])swap(t,dp[u][0]);
        if(t>dp[u][1])swap(t,dp[u][1]);
    }
    if(dp[u][0]+dp[u][1]>ans){
        ans=dp[u][0]+dp[u][1];
        rs1=dp[u][0];rs2=dp[u][1];
        rt=u;
    }
}bool vis[mxn]{0};
vector<pair<ll,int>>vec[mxn];
void dfs2(int u,int p,ll w){
    if(g[u].size()==1)vec[u].pb({0,u});
    for(auto [v,w]:g[u]){
        if(v==p)continue;
        dfs2(v,u,w);
        if(!vec[u].empty()&&!vec[v].empty()&&vec[u].back()>vec[v].back())vec[v].pb(vec[u].back()),vec[u].pop_back();
        for(auto it : vec[v])vec[u].pb(it);
    }vec[u].back().f+=w;add[vec[u].back().s]+=w;
}
bool ch(int u,int p){
    for(auto [v,w]:g[u]){
        if(v==p)continue;
        if(ch(v,u))vis[u]=1;
    }return vis[u];
}ll res[mxn]{0};
vector<ll>vv[mxn];
ll sm[mxn]{0};
void solve1(int u,int p,ll d){
    if(g[u].size()==1)vv[u].pb(0);
    for(auto [v,w]:g[u]){
        if(v==p||!vis[v])continue;
        solve1(v,u,w);
        if(!vv[u].empty()&&!vv[v].empty()&&vv[u].back()>vv[v].back())vv[v].pb(vv[u].back()),vv[u].pop_back();
        for(auto it : vv[v])vv[u].pb(it);
        sm[u]+=sm[v];
    }
    res[u]=ans-sm[u];int k=vv[u].size();
    vector<ll>v;
    for(auto it : vec[rt])v.pb(it.f);
    for(auto it : vv[u])v.pb(it);
    sort(all(v));
    while(k>0){
        res[u]+=v.back();v.pop_back();k--;
    }sm[u]+=d;vv[u].back()+=d;
}
ll d[mxn]{0};
ll di[mxn]{0};
ll curmx=0,curme;
void cal(int u,int p){
    if(d[u]>curmx){
        curmx=d[u],curme=u;
    }
    for(auto [v,w]:g[u]){
        if(v==p)continue;
        d[v]=d[u]+w;
        cal(v,u);
    }
}
void solve1(int n){
    cal(1,1);
    int rrt=curme;
    memset(d,0,sizeof d);
    curmx=curme=0;
    cal(rrt,rrt);
    for(int i=1;i<=n;i++)di[i]=max(di[i],d[i]);
    memset(d,0,sizeof d);rrt=curme;
    cal(rrt,rrt);
    for(int i=1;i<=n;i++)di[i]=max(di[i],d[i]);
    for(int i=1;i<=n;i++)cout<<di[i]<<'\n';
    return;
}
void solve2(int u,int p,ll d){
    if(!vis[u])res[u]=res[p]+d;
    for(auto [v,w]:g[u]){
        if(v==p)continue;
        solve2(v,u,w);
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,k;cin>>n>>k;
    for(int i=1;i<=n-1;i++){
        int u,v,w;cin>>u>>v>>w;
        g[u].pb({v,w});
        g[v].pb({u,w});
    }if(k==1){solve1(n);return 0;}
    for(int i=1;i<=n;i++)if(g[i].size()>1)rt=i;
    dfs(rt,rt);dfs2(rt,rt,0);
    for(int j=0;j<vec[rt].size();j++){
        if(vec[rt][j].f==rs1){vis[vec[rt][j].s]=1,swap(vec[rt][j],vec[rt].back());break;}
    }vec[rt].pop_back();k-=2;
    for(int j=0;j<vec[rt].size();j++){
        if(vec[rt][j].f==rs2){vis[vec[rt][j].s]=1,swap(vec[rt][j],vec[rt].back());break;}
    }vec[rt].pop_back();sort(all(vec[rt]));
    while(k>0&&!vec[rt].empty()){
        ans+=vec[rt].back().f;
        vis[vec[rt].back().s]=1;vec[rt].pop_back();k--;
    }reverse(all(vec[rt]));
    ch(rt,rt);solve1(rt,rt,0);solve2(rt,rt,0);
    for(int i=1;i<=n;i++)cout<<res[i]<<'\n';
}

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32