Submission #2666733


Source Code Expand

#include <bits/stdc++.h>
#define MOD 1000000007
#define int long long
#define pb push_back
#define bw(i,r,l) for (int i=r-1;i>=l;i--)
#define fw(i,l,r) for (int i=l;i<r;i++)
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> edge;
const int N=100005;
int n,par[N],sz[N],ans[N],lazy[N]; vector<edge> e; vector<int> child[100001];
int getp(int u) {
	if (u==par[u]) return u;
	return par[u]=getp(par[u]);
}
void joint(int u,int v,int val) {
	if (sz[u]>sz[v]) swap(u,v);
	//Now we only have to merge u into v
	while (child[u].size()) {
		child[v].pb(child[u].back());
		int temp=child[u].back();
		if (lazy[u]) ans[temp]+=lazy[u];
		ans[temp]+=val*sz[v];
		ans[temp]-=val*sz[u];
		ans[temp]-=lazy[v];
		child[u].pop_back();
	}
	lazy[v]+=sz[u]*val;
	sz[v]+=sz[u];
	par[u]=v;
}
signed main() {
	//freopen("aome.inp","r",stdin);
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n;
	fw (i,1,n) {
		int a,b,c; cin>>a>>b>>c; a--; b--;
		e.pb(edge(c,ii(a,b)));
	}
	sort(e.begin(),e.end());
	reverse(e.begin(),e.end());
	/*
	Idea: Sort all edges based on their c values. Then if a and b doesn't belong to the same group,
	every item in b will connect to every item in a with a cost ofc.
	Merge the smaller group into the bigger one, so each item will be merged exactly log(N) times.
	To update the smaller group, just do it manually. To update the bigger group, we keep a lazy value
	for it, so if we need to update it later when merging we will also perform the lazy update.
	Call the larger group u, smaller one v. Every item in v is added c * sz[u], and otherwise.
	To successfully use lazy, erase all the elements in v by the supposed lazy value we will add.
	*/
	fw (i,0,n) {
		child[i].pb(i);
		sz[i]=1;
		par[i]=i;
		ans[i]=0;
		lazy[i]=0;
	}
	fw (i,0,e.size()) {
		int c=e[i].first,u=e[i].second.first,v=e[i].second.second;
		int pu=getp(u),pv=getp(v);
		if (pu==pv) continue;
		joint(pu,pv,c);
	}
	fw (i,0,n) ans[i]+=lazy[getp(i)];
	fw (i,0,n) cout<<ans[i]<<"\n";
}

Submission Info

Submission Time
Task E - Black Cats Deployment
User vjudge2
Language C++14 (GCC 5.4.1)
Score 800
Code Size 1996 Byte
Status AC
Exec Time 77 ms
Memory 20464 KB

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 3 ms 4352 KB
00_example_02.txt AC 3 ms 4352 KB
00_example_03.txt AC 3 ms 4352 KB
s1_01.txt AC 3 ms 4480 KB
s1_02.txt AC 3 ms 4480 KB
s1_03.txt AC 3 ms 4352 KB
s1_04.txt AC 3 ms 4480 KB
s1_05.txt AC 3 ms 4480 KB
s1_06.txt AC 3 ms 4480 KB
s1_07.txt AC 3 ms 4352 KB
s2_08.txt AC 56 ms 13680 KB
s2_09.txt AC 28 ms 9332 KB
s2_10.txt AC 17 ms 6904 KB
s2_11.txt AC 64 ms 14832 KB
s2_12.txt AC 68 ms 16368 KB
s2_13.txt AC 71 ms 20080 KB
s2_14.txt AC 71 ms 19952 KB
s3_15.txt AC 62 ms 14576 KB
s3_16.txt AC 31 ms 9588 KB
s3_17.txt AC 18 ms 7032 KB
s3_18.txt AC 30 ms 9204 KB
s3_19.txt AC 70 ms 15856 KB
s3_20.txt AC 74 ms 16752 KB
s3_21.txt AC 71 ms 15600 KB
s3_22.txt AC 70 ms 15600 KB
s3_23.txt AC 77 ms 20464 KB
s3_24.txt AC 72 ms 19568 KB
s3_25.txt AC 56 ms 14448 KB
s3_26.txt AC 71 ms 19056 KB
s3_27.txt AC 56 ms 15216 KB
s3_28.txt AC 69 ms 19056 KB
s3_29.txt AC 57 ms 14448 KB