Submission #2667660


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 vjudge4
Language Bash (GNU bash v4.3.11)
Score 0
Code Size 1567 Byte
Status RE
Exec Time 6 ms
Memory 632 KB

Judge Result

Set Name Sample Subtask1 Subtask2 All
Score / Max Score 0 / 0 0 / 200 0 / 200 0 / 400
Status
RE × 3
RE × 10
RE × 9
RE × 32
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
Subtask1 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt
Subtask2 00_example_02.txt, s1_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt, s2_13.txt, s2_14.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt, s2_13.txt, s2_14.txt, s3_15.txt, s3_16.txt, s3_17.txt, s3_18.txt, s3_19.txt, s3_20.txt, s3_21.txt, s3_22.txt, s3_23.txt, s3_24.txt, s3_25.txt, s3_26.txt, s3_27.txt, s3_28.txt, s3_29.txt
Case Name Status Exec Time Memory
00_example_01.txt RE 6 ms 608 KB
00_example_02.txt RE 6 ms 608 KB
00_example_03.txt RE 6 ms 632 KB
s1_01.txt RE 6 ms 608 KB
s1_02.txt RE 6 ms 608 KB
s1_03.txt RE 6 ms 608 KB
s1_04.txt RE 6 ms 608 KB
s1_05.txt RE 6 ms 608 KB
s1_06.txt RE 6 ms 608 KB
s1_07.txt RE 6 ms 608 KB
s2_08.txt RE 6 ms 608 KB
s2_09.txt RE 6 ms 632 KB
s2_10.txt RE 6 ms 632 KB
s2_11.txt RE 6 ms 608 KB
s2_12.txt RE 6 ms 604 KB
s2_13.txt RE 6 ms 608 KB
s2_14.txt RE 6 ms 608 KB
s3_15.txt RE 6 ms 612 KB
s3_16.txt RE 6 ms 632 KB
s3_17.txt RE 6 ms 632 KB
s3_18.txt RE 6 ms 608 KB
s3_19.txt RE 6 ms 608 KB
s3_20.txt RE 6 ms 628 KB
s3_21.txt RE 6 ms 608 KB
s3_22.txt RE 6 ms 608 KB
s3_23.txt RE 6 ms 608 KB
s3_24.txt RE 6 ms 604 KB
s3_25.txt RE 6 ms 632 KB
s3_26.txt RE 6 ms 608 KB
s3_27.txt RE 6 ms 608 KB
s3_28.txt RE 6 ms 612 KB
s3_29.txt RE 6 ms 604 KB