Submission #1289239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289239		ar_tkinter	Paths (RMI21_paths)	C++20	12 / 100	47 ms	13960 KiB

Main

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

struct E { int v; ll w; };
const int N = 100000;
int n,k;
vector<E> g[N+1];
ll dn[N+1], up[N+1], a1[N+1], a2[N+1];
int ch[N+1];

void f1(int u,int p){
    a1[u]=a2[u]=0;
    for(auto [v,w]:g[u]) if(v!=p){
        f1(v,u);
        ll x=dn[v]+w;
        if(x>a1[u]){a2[u]=a1[u];a1[u]=x;ch[u]=v;}
        else if(x>a2[u]) a2[u]=x;
    }
    dn[u]=a1[u];
}
void f2(int u,int p){
    for(auto [v,w]:g[u]) if(v!=p){
        ll y=(ch[u]==v?a2[u]:a1[u]);
        up[v]=max(up[u],y)+w;
        f2(v,u);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k;
    for(int i=0;i<n-1;i++){
        int a,b; ll w;
        cin>>a>>b>>w;
        g[a].push_back({b,w});
        g[b].push_back({a,w});
    }
    f1(1,0);
    up[1]=0;
    f2(1,0);
    for(int i=1;i<=n;i++)
        cout<<max(dn[i],up[i])<<(i==n?'\n':' ');
}

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