# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
82815 | 2018-11-01T20:42:51 Z | farukkastamonuda | Inspection (POI11_ins) | C++14 | 2421 ms | 132096 KB |
#include <cstdio> #include <vector> #include <queue> #include <cassert> #include <bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 1000123; const int NOANS = -1; int deg[MAXN]; vector<int> v[MAXN]; int n; bool used[MAXN]; int myDeg[MAXN], father[MAXN], sizeOfSubtree[MAXN], depth[MAXN], maxSubtree[MAXN]; LL cost[MAXN]; queue<int> q; vector<int> cands; vector<int> getCandidates; void dfs(int x) { used[x] = true; for(int i = 0; i < (int)v[x].size(); i ++) if (!used[v[x][i]]) { father[v[x][i]] = x; dfs(v[x][i]); } } vector<int> getCands(int root) { 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); 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) { 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); 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(int i = 0; i < (int)v[root].size(); i ++) { maxDepth = std::max(maxDepth, depth[v[root][i]]); } for(int i = 0; i < (int)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] ++; } 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 | 23 ms | 23928 KB | Output is correct |
2 | Correct | 23 ms | 24052 KB | Output is correct |
3 | Correct | 23 ms | 24196 KB | Output is correct |
4 | Correct | 23 ms | 24196 KB | Output is correct |
5 | Correct | 23 ms | 24196 KB | Output is correct |
6 | Correct | 24 ms | 24196 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 24196 KB | Output is correct |
2 | Correct | 23 ms | 24196 KB | Output is correct |
3 | Correct | 24 ms | 24196 KB | Output is correct |
4 | Correct | 26 ms | 24196 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 24196 KB | Output is correct |
2 | Correct | 25 ms | 24288 KB | Output is correct |
3 | Correct | 25 ms | 24304 KB | Output is correct |
4 | Correct | 24 ms | 24304 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 42 ms | 25576 KB | Output is correct |
2 | Correct | 39 ms | 25736 KB | Output is correct |
3 | Correct | 41 ms | 26000 KB | Output is correct |
4 | Correct | 92 ms | 26000 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 57 ms | 26920 KB | Output is correct |
2 | Correct | 55 ms | 27320 KB | Output is correct |
3 | Correct | 56 ms | 27816 KB | Output is correct |
4 | Correct | 52 ms | 27816 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 126 ms | 31068 KB | Output is correct |
2 | Correct | 128 ms | 32168 KB | Output is correct |
3 | Correct | 123 ms | 33564 KB | Output is correct |
4 | Correct | 106 ms | 33564 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 932 ms | 59052 KB | Output is correct |
2 | Correct | 898 ms | 64380 KB | Output is correct |
3 | Correct | 955 ms | 70344 KB | Output is correct |
4 | Correct | 826 ms | 70344 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2421 ms | 93792 KB | Output is correct |
2 | Correct | 2380 ms | 104552 KB | Output is correct |
3 | Correct | 2226 ms | 115980 KB | Output is correct |
4 | Correct | 1948 ms | 115980 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2244 ms | 115980 KB | Output is correct |
2 | Correct | 2047 ms | 115980 KB | Output is correct |
3 | Correct | 2020 ms | 118384 KB | Output is correct |
4 | Correct | 1669 ms | 118384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2160 ms | 118384 KB | Output is correct |
2 | Runtime error | 2323 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 | - |