Submission #2667672


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>ii;
typedef pair<int,ii>iii;
typedef vector<int>vi;
vector<vi>adjlist;
vector<iii>edge;
const int N=1e5+5;
long long ans[N],lazy[N];
int pa[N],sz[N];
void unionset(int x,int y,int w)
{
    x=pa[x];
    y=pa[y];
    if(sz[x]<sz[y]){
        lazy[y]+=sz[x]*w;
        for(int i=0;i<adjlist[x].size();++i){
            int v=adjlist[x][i];
            pa[v]=y;
            adjlist[y].push_back(v);
            ans[v]+=lazy[x];
            ans[v]+=sz[y]*w;
            ans[v]-=lazy[y];
        }
        sz[y]+=sz[x];
    }
    else{
        lazy[x]+=sz[y]*w;
        for(int i=0;i<adjlist[y].size();++i){
            int v=adjlist[y][i];
            pa[v]=x;
            adjlist[x].push_back(v);
            ans[v]+=lazy[y];
            ans[v]+=sz[x]*w;
            ans[v]-=lazy[x];
        }
        sz[x]+=sz[y];
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    adjlist.assign(n+1,vi());
    for(int i=1;i<=n;++i){
        adjlist[i].push_back(i);
        pa[i]=i;
        sz[i]=1;
    }
    for(int i=1;i<n;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        edge.push_back(iii(w,ii(u,v)));
    }
    sort(edge.begin(),edge.end());
    reverse(edge.begin(),edge.end());
    for(int i=0;i<edge.size();++i){
        unionset(edge[i].second.first,edge[i].second.second,edge[i].first);
    }
    int root=0;
    for(int i=1;i<=n;++i)if(pa[i]==i)root=i;
    for(int i=0;i<adjlist[root].size();i++)ans[adjlist[root][i]]+=lazy[root];
    for(int i=1;i<=n;++i)printf("%lld\n",ans[i]);
}

Submission Info

Submission Time
Task E - Black Cats Deployment
User vjudge2
Language C++14 (Clang 3.8.0)
Score 0
Code Size 1567 Byte
Status CE

Compile Error

./Main.cpp:1:9: fatal error: 'bits/stdc++.h' file not found
#include<bits/stdc++.h>
        ^
1 error generated.