| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 82807 | 2018-11-01T20:21:13 Z | farukkastamonuda | Inspection (POI11_ins) | C++14 | 2053 ms | 132096 KB |
/*************************************************************************
* *
* XVIII Olimpiada Informatyczna *
* *
* Zadanie: Inspekcja *
* Autor: Miroslaw Michalski *
* Zlozonosc czasowa: O(n) *
* Opis: Rozwiazanie wzorcowe - sprytniejsze *
* *
*************************************************************************/
#include <cstdio>
#include <vector>
#include <queue>
#include <cassert>
typedef long long LL; // tylko po to aby sprawdzic jak zachowa sie dla intow
const int MAXN = 1000123;
const int NOANS = -1;
int deg[MAXN];
std::vector<int> v[MAXN];
int n;
bool used[MAXN];
int myDeg[MAXN], father[MAXN], sizeOfSubtree[MAXN], depth[MAXN], maxSubtree[MAXN];
LL cost[MAXN];
void dfs(int x) {
used[x] = true;
for(size_t i = 0; i < v[x].size(); i++) if (!used[v[x][i]]) {
father[v[x][i]] = x;
dfs(v[x][i]);
}
}
std::vector<int> getCands(int root) {
std::vector<int> cands;
for(int i = 0; i < n; i++) {
myDeg[i] = deg[i];
used[i] = false;
father[i] = -1;
sizeOfSubtree[i] = 1;
maxSubtree[i] = 0;
}
dfs(root);
std::queue<int> q;
for(int i = 0; i < n; i++) if (myDeg[i] == 1) {
q.push(i);
}
while (!q.empty()) {
int wz1 = q.front(); q.pop();
myDeg[father[wz1]]--;
if (std::max(n - sizeOfSubtree[wz1], maxSubtree[wz1]) <= n/2) {
cands.push_back(wz1);
}
sizeOfSubtree[father[wz1]] += sizeOfSubtree[wz1];
maxSubtree[father[wz1]] = std::max(maxSubtree[father[wz1]], sizeOfSubtree[wz1]);
if (myDeg[father[wz1]] == 1 && father[wz1] != -1) {
q.push(father[wz1]);
}
}
return cands;
}
LL anal(int root) {
// liczymy odpowiedz dla root'a max. poddrzewo == n/2
for(int i = 0; i < n; i++) {
myDeg[i] = deg[i];
used[i] = false;
father[i] = -1;
sizeOfSubtree[i] = 1;
cost[i] = 0;
depth[i] = 0;
}
dfs(root);
std::queue<int> q;
for(int i = 0; i < n; i++) if (myDeg[i] == 1) {
q.push(i);
}
while (!q.empty()) {
int wz1 = q.front(); q.pop();
myDeg[father[wz1]]--;
sizeOfSubtree[father[wz1]] += sizeOfSubtree[wz1];
cost[father[wz1]] += (2L * sizeOfSubtree[wz1] + cost[wz1]);
depth[father[wz1]] = std::max(depth[father[wz1]], depth[wz1] + 1);
if (myDeg[father[wz1]] == 1 && father[wz1] != -1) {
q.push(father[wz1]);
}
}
int maxDepth = 0;
for(size_t i = 0; i < v[root].size(); i++) {
maxDepth = std::max(maxDepth, depth[v[root][i]]);
}
for(size_t i = 0; i < v[root].size(); i++) {
if (sizeOfSubtree[v[root][i]] == n/2) {
maxDepth = depth[v[root][i]];
}
}
return cost[root] - (maxDepth + 1);
}
int main() {
int a, b;
scanf("%d", &n);
if (n == 1) {
printf("0\n");
return 0;
}
for(int i = 0; i < n - 1; i++) {
scanf("%d %d", &a, &b);
a--; b--;
v[a].push_back(b);
v[b].push_back(a);
deg[a]++;
deg[b]++;
}
std::vector<int> getCandidates = getCands(n - 1);
if (getCandidates.size() == 1) {
int a = getCandidates[0];
for(int i = 0; i < a; i++) {
printf("%d\n", NOANS);
}
printf("%lld\n", anal(a));
for(int i = a + 1; i < n; i++) {
printf("%d\n", NOANS);
}
} else if (getCandidates.size() == 2) {
int a = getCandidates[0], b = getCandidates[1];
if (a > b) std::swap(a, b);
for(int i = 0; i < a; i++) {
printf("%d\n", NOANS);
}
printf("%lld\n", anal(a));
for(int i = a + 1; i < b; i++) {
printf("%d\n", NOANS);
}
printf("%lld\n", anal(b));
for(int i = b + 1; i < n; i++) {
printf("%d\n", NOANS);
}
} else {
assert(false);
}
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 22 ms | 23800 KB | Output is correct |
| 2 | Correct | 22 ms | 24016 KB | Output is correct |
| 3 | Correct | 23 ms | 24044 KB | Output is correct |
| 4 | Correct | 24 ms | 24204 KB | Output is correct |
| 5 | Correct | 23 ms | 24204 KB | Output is correct |
| 6 | Correct | 23 ms | 24204 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 22 ms | 24204 KB | Output is correct |
| 2 | Correct | 23 ms | 24204 KB | Output is correct |
| 3 | Correct | 22 ms | 24204 KB | Output is correct |
| 4 | Correct | 23 ms | 24384 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 26 ms | 24384 KB | Output is correct |
| 2 | Correct | 25 ms | 24444 KB | Output is correct |
| 3 | Correct | 24 ms | 24484 KB | Output is correct |
| 4 | Correct | 24 ms | 24520 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 39 ms | 25708 KB | Output is correct |
| 2 | Correct | 40 ms | 26092 KB | Output is correct |
| 3 | Correct | 38 ms | 26436 KB | Output is correct |
| 4 | Correct | 37 ms | 26436 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 61 ms | 27768 KB | Output is correct |
| 2 | Correct | 60 ms | 28404 KB | Output is correct |
| 3 | Correct | 56 ms | 29232 KB | Output is correct |
| 4 | Correct | 80 ms | 29232 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 120 ms | 33252 KB | Output is correct |
| 2 | Correct | 115 ms | 35160 KB | Output is correct |
| 3 | Correct | 126 ms | 37176 KB | Output is correct |
| 4 | Correct | 105 ms | 37176 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 836 ms | 64664 KB | Output is correct |
| 2 | Correct | 753 ms | 74664 KB | Output is correct |
| 3 | Correct | 757 ms | 84764 KB | Output is correct |
| 4 | Correct | 619 ms | 84764 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2012 ms | 118512 KB | Output is correct |
| 2 | Runtime error | 1956 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. |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 2052 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 | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 2053 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 | - |