Submission #2666738


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct edge{
	int u,v;
	long long w;
	edge(int a,int b,long long c):u(a),v(b),w(c){}
};
long long lazy[N],res[N];
int n,p[N];
vector<vector<int> > sets;
vector<edge> E;
bool cmp(edge &a,edge &b){
	return a.w<b.w;
}
void dsu(int i,int j,long long w){
	for(int k=0;k<sets[i].size();k++){
		res[sets[i][k]]+=lazy[i]-lazy[j]+w*sets[j].size();
		p[sets[i][k]]=j;
	}
	for(int k=0;k<sets[i].size();k++){
		sets[j].push_back(sets[i][k]);
	}
	sets[i].clear();
}
int main(){
	scanf("%d",&n);
	sets.assign(n+1,vector<int>());
	for(int i=1;i<=n;i++){
		p[i]=i;
		sets[i].push_back(i);
	}
	for(int i=1;i<n;i++){
		int u,v;
		long long w;
		cin>>u>>v>>w;
		E.push_back(edge(u,v,w));
	}
	sort(E.begin(),E.end(),cmp);
	reverse(E.begin(),E.end());
	for(int i=0;i<E.size();i++){
		int u=p[E[i].u];
		int v=p[E[i].v];
		int w=E[i].w;
		if(sets[u].size()>sets[v].size()){
			swap(u,v);
		}
		lazy[v]+=w*sets[u].size();
		dsu(u,v,w);
	}
	for(int i=1;i<=n;i++){
		cout<<res[i]+lazy[p[i]]<<"\n";
	}
}

Submission Info

Submission Time
Task E - Black Cats Deployment
User vjudge3
Language C++14 (GCC 5.4.1)
Score 800
Code Size 1046 Byte
Status AC
Exec Time 152 ms
Memory 14448 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:27:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^

Judge Result

Set Name Sample Subtask1 Subtask2 All
Score / Max Score 0 / 0 200 / 200 200 / 200 400 / 400
Status
AC × 3
AC × 10
AC × 9
AC × 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 AC 1 ms 256 KB
00_example_02.txt AC 1 ms 256 KB
00_example_03.txt AC 1 ms 256 KB
s1_01.txt AC 2 ms 384 KB
s1_02.txt AC 2 ms 384 KB
s1_03.txt AC 2 ms 256 KB
s1_04.txt AC 2 ms 384 KB
s1_05.txt AC 2 ms 384 KB
s1_06.txt AC 2 ms 384 KB
s1_07.txt AC 1 ms 256 KB
s2_08.txt AC 94 ms 9968 KB
s2_09.txt AC 46 ms 4980 KB
s2_10.txt AC 26 ms 3068 KB
s2_11.txt AC 111 ms 11120 KB
s2_12.txt AC 110 ms 11120 KB
s2_13.txt AC 112 ms 12272 KB
s2_14.txt AC 109 ms 13040 KB
s3_15.txt AC 124 ms 10736 KB
s3_16.txt AC 61 ms 5620 KB
s3_17.txt AC 34 ms 3196 KB
s3_18.txt AC 60 ms 5368 KB
s3_19.txt AC 142 ms 12144 KB
s3_20.txt AC 146 ms 12528 KB
s3_21.txt AC 147 ms 12016 KB
s3_22.txt AC 147 ms 12016 KB
s3_23.txt AC 152 ms 14448 KB
s3_24.txt AC 146 ms 13936 KB
s3_25.txt AC 128 ms 10864 KB
s3_26.txt AC 144 ms 13680 KB
s3_27.txt AC 124 ms 10864 KB
s3_28.txt AC 146 ms 13680 KB
s3_29.txt AC 131 ms 10864 KB