Submission #76100

#	Time	Username	Problem	Language	Result	Execution time	Memory
76100		thebes	Untitled (POI11_ins)	C++14	0 / 100	1512 ms	132096 KiB

Main

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

const int MN = 1e6+6;
int N, i, x, y, sz[MN];
long long sum[MN], ans[MN];
vector<int> adj[MN];
pair<int,int> a[MN], b[MN], mx[MN];

void dfs1(int n, int p){
	sz[n] = 1;
	for(auto v : adj[n]){
		if(v == p) continue;
		dfs1(v, n);
		pair<int,int> w={sz[v],v};
		sz[n] += sz[v];
		if(w.first>a[n].first) b[n]=a[n],a[n]=w;
		else if(w.first>b[n].first) b[n]=w;
		if(w.first>mx[n].first) mx[n]=w;
		sum[n] += sum[v]+sz[v];
	}
}

void dfs2(int n, int p, int as, long long asum, int u){
	if(max(mx[n].first,as)<=(N-1)/2+((N-1)%2)){
		if(N%2==0&&max(mx[n].first,as)==(N-1)/2+((N-1)%2))
			ans[n] = 2*(sum[n]+asum)-a[mx[n].second].first-1;
		else ans[n] = 2*(sum[n]+asum)-max(u,a[n].first);
	}
	else ans[n] = -1;
	for(auto v : adj[n]){
		if(v == p) continue;
		if(v == a[n].second) dfs2(v, n, N-sz[v], asum+sum[n]-sum[v]+N-2*sz[v], max(u,b[n].first)+1);
		else dfs2(v, n, N-sz[v], asum+sum[n]-sum[v]+N-2*sz[v], max(u,a[n].first)+1);
	}
}

int main(){
	for(scanf("%d",&N),i=1;i<N;i++){
		scanf("%d%d",&x,&y);
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	dfs1(1, 0); dfs2(1, 0, 0, 0, 0);
	for(i=1;i<=N;i++) printf("%lld\n",ans[i]);
	return 0;
}

Compilation message (stderr)

ins.cpp: In function 'int main()':
ins.cpp:39:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(scanf("%d",&N),i=1;i<N;i++){
      ~~~~~~~~~~~~~~^~~~
ins.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10