oj.uz

Submission #76100

# Submission time Handle Problem Language Result Execution time Memory
76100 2018-09-12T04:42:41 Z thebes Inspection (POI11_ins) C++14
0 / 100
 1512 ms 132096 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 24056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 24056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 24220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 26036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 27984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 33952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 702 ms 71984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1512 ms 124708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1511 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1494 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -