제출 #286430

#제출 시각아이디문제언어결과실행 시간메모리
286430AaronNaidu도시들 (IOI15_towns)C++14
13 / 100
39 ms5112 KiB
#include <bits/stdc++.h> #include "towns.h" using namespace std; int n; int dists[111][111]; int fullDists[1000][1000]; int distToRoot[1000]; int lcaHeights[111][111]; vector<pair<int, int> > tree[1000]; int pointer; vector<vector<int> > secretDistances; /*int getDistance(int i, int j) { return secretDistances[i][j]; }*/ void solveRegion(vector<int> leafs, int root, int rootHeight) { if (leafs.size() == 0) { return; } if (leafs.size() == 1) { int height = distToRoot[leafs[0]] - rootHeight; tree[root].push_back({leafs[0], height}); tree[leafs[0]].push_back({root, height}); return; } vector<int> part1, part2; int newRoot = pointer; pointer++; int newRootHeight = 1000000007; int firstInSet = leafs[0]; part1.push_back(firstInSet); for (int i = 1; i < leafs.size(); i++) { if (lcaHeights[firstInSet][leafs[i]] > rootHeight) { newRootHeight = min(newRootHeight, lcaHeights[firstInSet][leafs[i]]); part1.push_back(leafs[i]); } else { part2.push_back(leafs[i]); } } if (newRootHeight == 1000000007) { newRootHeight = rootHeight; newRoot = root; pointer--; } if (part1.size() > 1) { int newHeight = newRootHeight - rootHeight; tree[root].push_back({newRoot, newHeight}); tree[newRoot].push_back({root, newHeight}); } solveRegion(part1, newRoot, newRootHeight); solveRegion(part2, root, rootHeight); } int dfs(int node, int parent, int distance, int root) { //cout << "DFS on node " << node << "\n"; int maxDist = distance; fullDists[root][node] = distance; for (auto i : tree[node]) { if (i.first != parent) { //cout << "Spot " << i.first << " distance " << i.second << "away\n"; maxDist = max(maxDist, dfs(i.first, node, distance + i.second, root)); } } //cout << "Exit DFS on node " << node << "\n"; return maxDist; } /*void secret() { secretDistances.resize(11); for (int i = 0; i < 11; i++) { secretDistances[i].resize(11); } secretDistances[0] = {0, 17, 18, 20, 17, 12, 20, 16, 23, 20, 11}; secretDistances[1] = {17, 0, 23, 25, 22, 17, 25, 21, 28, 25, 16}; secretDistances[2] = {18, 23, 0, 12, 21, 16, 24, 20, 27, 24, 17}; secretDistances[3] = {20, 25, 12, 0, 23, 18, 26, 22, 29, 26, 19}; secretDistances[4] = {17, 22, 21, 23, 0, 9, 21, 17, 26, 23, 16}; secretDistances[5] = {12, 17, 16, 18, 9, 0, 16, 12, 21, 18, 11}; secretDistances[6] = {20, 25, 24, 26, 21, 16, 0, 10, 29, 26, 19}; secretDistances[7] = {16, 21, 20, 22, 17, 12, 10, 0, 25, 22, 15}; secretDistances[8] = {23, 28, 27, 29, 26, 21, 29, 25, 0, 21, 22}; secretDistances[9] = {20, 25, 24, 26, 23, 18, 26, 22, 21, 0, 19}; secretDistances[10] = {11, 16, 17, 19, 16, 11, 19, 15, 22, 19, 0}; }*/ int hubDistance(int N, int sub) { //secret(); n = N; pointer = 200; for (int i = 0; i < 1000; i++) { tree[i].clear(); distToRoot[i] = -1; for (int j = 0; j < 1000; j++) { fullDists[i][j] = -1; } } for (int i = 1; i < n; i++) { for (int j = i+1; j < n; j++) { dists[i][j] = getDistance(i, j); dists[j][i] = dists[i][j]; } } for (int i = 1; i < n; i++) { distToRoot[i] = getDistance(i, 0); } int minHeight = 1000000007; for (int i = 1; i < n; i++) { for (int j = i+1; j < n; j++) { lcaHeights[i][j] = (distToRoot[i] + distToRoot[j] - dists[i][j])/2; lcaHeights[j][i] = lcaHeights[i][j]; minHeight = min(minHeight, lcaHeights[i][j]); } } tree[0].push_back({pointer, minHeight}); tree[pointer].push_back({0, minHeight}); pointer++; vector<int> s; for (int i = 1; i < n; i++) { s.push_back(i); } solveRegion(s, pointer-1, minHeight); int minMax = 1000000007; for (int i = 200; i < pointer; i++) { minMax = min(dfs(i, -1, 0, i),minMax); } return minMax; }

컴파일 시 표준 에러 (stderr) 메시지

towns.cpp: In function 'void solveRegion(std::vector<int>, int, int)':
towns.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 1; i < leafs.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:99:28: warning: unused parameter 'sub' [-Wunused-parameter]
   99 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...