제출 #526927

#제출 시각아이디문제언어결과실행 시간메모리
526927LFFB경주 (Race) (IOI11_race)C++17
0 / 100
13 ms23772 KiB
#include <iostream> #include <vector> #include <string> #define debug(args...) //printf(args) typedef std::pair<int, int> intPair; #define forAllChild(node, code) for (intPair childPair : neighbors[node]) {\ int child = childPair.first;\ int childWeight = childPair.second;\ if (child == parent.get(node)) continue;\ if (removed.get(child)) continue;\ code;\ } const int MAX_N = 1000000 + 1; const int INF = 1000000000; template<typename T> class SpecialVector { private: int time; T values[MAX_N]; T standard; int lastChanged[MAX_N]; public: SpecialVector(T val) { time = 1; standard = val; } T get(int i) { if (i >= MAX_N) return standard; if (lastChanged[i] == time) return values[i]; return standard; } void set(int i, T v) { if (i >= MAX_N) return; values[i] = v; lastChanged[i] = time; } bool defined(int i) { if (i >= MAX_N) return false; return lastChanged[i] == time; } void clear() { time++; } }; int n; int k; std::vector<intPair> neighbors[MAX_N]; SpecialVector<int> parent(-1); SpecialVector<int> parentWeight(-1); SpecialVector<bool> removed(false); SpecialVector<int> lengths(-1); SpecialVector<int> lengthMap(-1); namespace CentroidDecomposition { int findBetterCentroid(int node, int root) { forAllChild(node, { if (lengths.get(child) > lengths.get(root)/2) return child; }); return -1; } int findCentroid(int root) { int node = root; while (findBetterCentroid(node, root) != -1) { debug("found better centroid for %d (root: %d)\n", node, root); node = findBetterCentroid(node, root); } debug("root %d, found centroid %d\n", root, node); return node; } } void setMin(int &a, int b) { a = std::min(a, b); } void findParents(int node) { lengths.set(node, 1); forAllChild(node, { parent.set(child, node); parentWeight.set(child, childWeight); findParents(child); lengths.set(node, lengths.get(node) + lengths.get(child)); }); } int getMin(int node, int depth, int distance) { int minimum; if (lengthMap.defined(k - distance)) { minimum = depth + lengthMap.get(k - distance); } else { minimum = INF; } forAllChild(node, { int childMinumum = getMin(child, depth + 1, distance + childWeight); setMin(minimum, childMinumum); }); return minimum; } void addToMapping(int node, int depth, int distance) { if (lengthMap.get(distance) > depth || !lengthMap.defined(distance)) { lengthMap.set(distance, depth); } forAllChild(node, { addToMapping(child, depth + 1, distance + childWeight); }); } int getMinimumLength(int root) { parent.clear(); lengths.clear(); findParents(root); int centroid = CentroidDecomposition::findCentroid(root); removed.set(centroid, true); lengthMap.clear(); lengths.clear(); parent.clear(); int minimum = INF; for (intPair neighborPair : neighbors[centroid]) { int neighbor = neighborPair.first; int neighborWeight = neighborPair.second; if (removed.get(neighbor)) continue; findParents(neighbor); int neighborMinimum = getMin(neighbor, 1, neighborWeight); setMin(minimum, neighborMinimum); addToMapping(neighbor, 1, neighborWeight); } for (intPair neighborPair : neighbors[centroid]) { int neighbor = neighborPair.first; int neighborWeight = neighborPair.second; if (removed.get(neighbor)) continue; int neighborMinimum = getMinimumLength(neighbor); setMin(minimum, neighborMinimum); } debug("root %d, centroid %d, returning %d\n", root, centroid, minimum); return minimum; } void printRepeated(std::string s, int x) { for (int i = 0; i < x; i++) printf("%s", s.c_str()); } void printTree(int node, int depth=0) { printRepeated("- ", depth); printf("%d\n", node); forAllChild(node, { printTree(child, depth + 1); }); } int best_path(int N, int K, int H[][2], int L[]) { n = N; k = K; for (int i = 0; i < n - 1; i++) { int a = H[i][0]; int b = H[i][1]; int w = L[i]; neighbors[a].push_back(std::make_pair(b, w)); neighbors[b].push_back(std::make_pair(a, w)); } //findParents(0); //printTree(0); int answer = getMinimumLength(0); return answer; }

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

race.cpp: In function 'int CentroidDecomposition::findBetterCentroid(int, int)':
race.cpp:12:9: warning: unused variable 'childWeight' [-Wunused-variable]
   12 |     int childWeight = childPair.second;\
      |         ^~~~~~~~~~~
race.cpp:76:9: note: in expansion of macro 'forAllChild'
   76 |         forAllChild(node, {
      |         ^~~~~~~~~~~
race.cpp: In function 'int getMinimumLength(int)':
race.cpp:166:13: warning: unused variable 'neighborWeight' [-Wunused-variable]
  166 |         int neighborWeight = neighborPair.second;
      |             ^~~~~~~~~~~~~~
race.cpp: In function 'void printTree(int, int)':
race.cpp:12:9: warning: unused variable 'childWeight' [-Wunused-variable]
   12 |     int childWeight = childPair.second;\
      |         ^~~~~~~~~~~
race.cpp:183:5: note: in expansion of macro 'forAllChild'
  183 |     forAllChild(node, {
      |     ^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...