oj.uz

Submission #26728

# Submission time Handle Problem Language Result Execution time Memory
26728 2017-07-05T10:38:47 Z model_code Inspection (POI11_ins) C++14
100 / 100
 2019 ms 109776 KB 
/*************************************************************************
 *                                                                       *
 *                    XVIII Olimpiada Informatyczna                      *
 *                                                                       *
 *   Zadanie:           Inspekcja                                        *
 *   Autor:             Dawid Dabrowski                                  *
 *   Zlozonosc czasowa: O(n)                                             *
 *   Opis:              Rozwiazanie wzorcowe - trudniejsze               *
 *                                                                       *
 *************************************************************************/

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 1000000;

int n;

vector<int> kra[MAXN]; // Wektor krawedzi.

int poddrzewo[MAXN], najglebszy_dol[MAXN], najglebszy_gora[MAXN], p[MAXN];
long long suma[MAXN];

// Dfs liczacy wielkosci poddrzew, sume odleglosci od potomkow oraz najdalszego potomka. Idzie od lisci do korzenia.
void dfs(int u) {
	poddrzewo[u] = 1;
	najglebszy_dol[u] = 0;
	for(int i=0; i<int(kra[u].size()); ++i) {
		if(kra[u][i] != p[u]) {
			p[kra[u][i]] = u;
			dfs(kra[u][i]);
			poddrzewo[u] += poddrzewo[kra[u][i]];
			najglebszy_dol[u] = max(najglebszy_dol[u], najglebszy_dol[kra[u][i]] + 1);
			suma[u] += suma[kra[u][i]] + poddrzewo[kra[u][i]];
		}
	}
}

// Dfs liczacy sume odleglosci od wszystkich wierzcholkow oraz najdalszy wierzcholek, do ktorego sciezka prowadzi przez ojca. Idzie od korzenia do lisci.
void dfs2(int u) {
	int mx1 = -1, mx2 = -1;
	for(int i=0; i<int(kra[u].size()); ++i) {
		if(kra[u][i] != p[u]) {
			if(najglebszy_dol[kra[u][i]] > mx1) {
				mx2 = mx1;
				mx1 = najglebszy_dol[kra[u][i]];
			} else if(najglebszy_dol[kra[u][i]] > mx2) {
				mx2 = najglebszy_dol[kra[u][i]];
			}
		}
	}
	// Magia :)
	for(int i=0; i<int(kra[u].size()); ++i) {
		if(kra[u][i] != p[u]) {
			suma[kra[u][i]] = suma[u] - 2*poddrzewo[kra[u][i]] + n;
			int best = mx1;
			if(najglebszy_dol[kra[u][i]] == mx1) {
				best = mx2;
			}
			najglebszy_gora[kra[u][i]] = max(najglebszy_gora[u]+1, max(1, best+2));
			dfs2(kra[u][i]);
		}
	}
}

int l;
int wiel[MAXN], najgl[MAXN];

int main() {
	scanf("%d", &n);
	// Budujemy graf.
	for(int i=0; i<n-1; ++i) {
		int u, v;
		scanf("%d %d", &u, &v);
		--u;
		--v;
		kra[u].push_back(v);
		kra[v].push_back(u);
	}
	p[0] = -1;
	// Liczymy odpowiednie wartosci dla kazdego wierzcholka.
	dfs(0);
	dfs2(0);
	
	// Jezeli ktos nie wierzy, to moze odkomentowac i zobaczyc, ze program dobrze liczy.
	/* for(int u=0; u<n; ++u) {
		printf("poddrzewo[%d] = %d\n",u+1,poddrzewo[u]);
		printf("najglebszy_dol[%d] = %d\n",u+1,najglebszy_dol[u]);
		printf("najglebszy_gora[%d] = %d\n",u+1,najglebszy_gora[u]);
		printf("suma_odleglosci[%d] = %lld\n",u+1,suma[u]);
	} */
	
	// Zgodnie z opracowaniem odpowiadamy na pytanie dla kazdego wierzcholka.
	for(int u=0; u<n; ++u) {
		l = 0;
		for(int i=0; i<int(kra[u].size()); ++i) { // Dla wygody dodajemy informacje o poddrzewach do osobnej tablicy.
			if(kra[u][i] != p[u]) {
				wiel[l] = poddrzewo[kra[u][i]];
				najgl[l] = najglebszy_dol[kra[u][i]];
				++l;
			} else {
				wiel[l] = n - poddrzewo[u];
				najgl[l] = najglebszy_gora[u] - 1;
				++l;
			}
		}
		long long best = 2*suma[u]; // W najgorszym razie przebedziemy dwa razy suma[u] (tak wlasciwie to 2*suma[u] - 1).
		bool ok=true; // ok <-> mozemy skonczyc w dowolnym poddrzewie 
		for(int i=0; i<l; ++i) {
			if(2*wiel[i] > n) { // Nie istnieje przechadzka, wynik ustawiamy na 0.
				best = -1;
				ok = false;
				break;
			}
			if(2*wiel[i] == n) { // Przechadzka istnieje, ale musimy skonczyc w najwiekszym poddrzewie, wiec ustawiamy odpowiednio wynik.
				best = 2*suma[u] - najgl[i] - 1;
				ok = false;
				break;
			}
		}
		if(ok) { // Jezeli mozemy skonczyc gdziekolwiek, to sprawdzamy, gdzie jest najlepiej.
			for(int i=0; i<l; ++i) {
				best = min(best, 2*suma[u] - najgl[i] - 1);
			}
		}
		printf("%lld\n",best); // Pamietamy o typie 64-bitowym :) i wypisujemy wynik.
	}
	return 0;
}

Compilation message

ins.cpp: In function 'int main()':
ins.cpp:72:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
ins.cpp:76:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
                         ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 55860 KB Output is correct
2 Correct 9 ms 55860 KB Output is correct
3 Correct 0 ms 55860 KB Output is correct
4 Correct 0 ms 55860 KB Output is correct
5 Correct 6 ms 55860 KB Output is correct
6 Correct 9 ms 55860 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 55860 KB Output is correct
2 Correct 9 ms 55860 KB Output is correct
3 Correct 6 ms 55860 KB Output is correct
4 Correct 9 ms 55860 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 55992 KB Output is correct
2 Correct 3 ms 55992 KB Output is correct
3 Correct 3 ms 55992 KB Output is correct
4 Correct 6 ms 55992 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 56520 KB Output is correct
2 Correct 16 ms 56704 KB Output is correct
3 Correct 23 ms 57020 KB Output is correct
4 Correct 23 ms 56520 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 57180 KB Output is correct
2 Correct 36 ms 57668 KB Output is correct
3 Correct 36 ms 58292 KB Output is correct
4 Correct 39 ms 57048 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 59160 KB Output is correct
2 Correct 99 ms 59836 KB Output is correct
3 Correct 113 ms 61100 KB Output is correct
4 Correct 116 ms 59056 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 863 ms 72096 KB Output is correct
2 Correct 829 ms 79648 KB Output is correct
3 Correct 733 ms 87332 KB Output is correct
4 Correct 756 ms 71720 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1899 ms 88200 KB Output is correct
2 Correct 1776 ms 103440 KB Output is correct
3 Correct 1783 ms 109776 KB Output is correct
4 Correct 1539 ms 87784 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1986 ms 88200 KB Output is correct
2 Correct 1849 ms 103436 KB Output is correct
3 Correct 1823 ms 109768 KB Output is correct
4 Correct 1709 ms 87784 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1996 ms 88200 KB Output is correct
2 Correct 1973 ms 103432 KB Output is correct
3 Correct 2019 ms 109776 KB Output is correct
4 Correct 1643 ms 87788 KB Output is correct