oj.uz

답안 #120502

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
120502 2019-06-24T17:13:39 Z popovicirobert Inspection (POI11_ins) C++14
90 / 100
 1807 ms 131072 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x)) 

using namespace std;

const int MAXN = (int) 1e6;

vector <int> g[MAXN + 1];
int down[MAXN + 1], sz[MAXN + 1];

void dfs(int nod, int par, ll &sum) {
	sz[nod] = 1;
	for(auto it : g[nod]) {
		if(it != par) {
			dfs(it, nod, sum);
			down[nod] = max(down[nod], down[it] + 1);
			sz[nod] += sz[it];
			sum += sz[it];
		}
	}
}

ll sol[MAXN + 1];
int n;

void solve(int nod, int par, ll sum, int mx_down) {

	int mx = n - sz[nod];
	multiset <int> mst;
	for(auto it : g[nod]) {
		if(it != par) {
			mx = max(mx, sz[it]);
			mst.insert(down[it]);
		}
	}

	if(mx <= (n - 1) - mx + 1) {
		if(mx < (n - 1) - mx + 1) {
			sol[nod] = 2LL * sum - max(mx_down, down[nod]);		
		}
		else {
			if(mx == n - sz[nod]) {
				sol[nod] = 2LL * sum - mx_down;
			}
			else {
				for(auto it : g[nod]) {
					if(it != par && sz[it] == mx) {
						sol[nod] = 2LL * sum - (down[it] + 1);
					}
				}
			}
		}
		//cerr << sum << " " << mx_down << " " << down[nod] << "\n";
	}
	else {
		sol[nod] = -1;
	}

	for(auto it : g[nod]) {
		if(it != par) {
			mst.erase(mst.find(down[it]));

			int cur = 0;
			if(mst.size()) {
				cur = *prev(mst.end());
			}

			solve(it, nod, sum - 2LL * sz[it] + n, max(mx_down + 1, cur + 2));
			mst.insert(down[it]);
		}
	}
}

int main() {
	//ifstream cin("A.in");
	//ofstream cout("A.out");
	int i; 
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	cin >> n;

	for(i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}

	ll sum = 0;
	dfs(1, 0, sum);
	solve(1, 0, sum, 0);
	
	for(i = 1; i <= n; i++) {
		cout << sol[i] << "\n";
	}

	return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 24 ms 23808 KB Output is correct
3 Correct 24 ms 23808 KB Output is correct
4 Correct 25 ms 23808 KB Output is correct
5 Correct 23 ms 23808 KB Output is correct
6 Incorrect 22 ms 23808 KB Output isn't correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 21 ms 23780 KB Output is correct
3 Correct 21 ms 23800 KB Output is correct
4 Correct 22 ms 23808 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 23 ms 24064 KB Output is correct
3 Correct 24 ms 24064 KB Output is correct
4 Correct 24 ms 24064 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 25080 KB Output is correct
2 Correct 36 ms 25796 KB Output is correct
3 Correct 39 ms 26588 KB Output is correct
4 Correct 38 ms 25212 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 26268 KB Output is correct
2 Correct 51 ms 27920 KB Output is correct
3 Correct 51 ms 29560 KB Output is correct
4 Correct 52 ms 26488 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 30236 KB Output is correct
2 Correct 126 ms 32464 KB Output is correct
3 Correct 129 ms 35528 KB Output is correct
4 Correct 120 ms 30328 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 853 ms 51112 KB Output is correct
2 Correct 870 ms 70608 KB Output is correct
3 Correct 797 ms 95096 KB Output is correct
4 Correct 748 ms 56440 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1789 ms 76656 KB Output is correct
2 Correct 1705 ms 127260 KB Output is correct
3 Correct 1709 ms 131072 KB Output is correct
4 Correct 1403 ms 89188 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1807 ms 76632 KB Output is correct
2 Correct 1714 ms 127256 KB Output is correct
3 Correct 1718 ms 131072 KB Output is correct
4 Correct 1412 ms 89332 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1768 ms 76604 KB Output is correct
2 Correct 1695 ms 127204 KB Output is correct
3 Correct 1692 ms 131072 KB Output is correct
4 Correct 1380 ms 89248 KB Output is correct