제출 #859668

#제출 시각아이디문제언어결과실행 시간메모리
859668lbadea1000경주 (Race) (IOI11_race)C++17
0 / 100
2 ms9560 KiB
#include <bits/stdc++.h> #include "race.h" using namespace std; const int NMAX = 1e5; const int INF = 1e9; int totalSize; vector<pair<int, int>> edges[NMAX]; vector<pair<long long, int>> distCentroidSubtree[NMAX]; int sz[NMAX]; int centroidParent[NMAX]; bool isIn[NMAX]; int dfsCalcSize(int node, int parent) { sz[node] = 1; for(auto child : edges[node]) { if(child.first != parent && isIn[child.first]) { sz[node] += dfsCalcSize(child.first, node); } } return sz[node]; } int dfsDetCentroid(int node, int parent) { for(auto child : edges[node]) { if(child.first != parent && sz[child.first] > totalSize / 2 && isIn[child.first]) { return dfsDetCentroid(child.first, node); } } return node; } void computeDist(int centroid, int node, int parent, int depth, long long sum) { distCentroidSubtree[centroid].push_back({sum, depth}); for(auto child : edges[node]) { if(isIn[child.first] && child.first != parent) { computeDist(centroid, child.first, node, depth + 1, sum + child.second); } } } void decompose(int root, int parent) { totalSize = dfsCalcSize(root, root); int centroid = dfsDetCentroid(root, root); computeDist(centroid, centroid, centroid, 0, 0); isIn[centroid] = false; centroidParent[centroid] = parent; for(auto child : edges[centroid]) { if(isIn[child.first]) decompose(child.first, centroid); } } bool cmp(pair<long long, int> a, pair<long long, int> b) { return a.first < b.first || (a.first == b.first && a.second < b.second); } int best_path(int n, int k, int h[][2], int len[]) { for(int i = 0; i < n - 1; i++) { edges[h[i][0]].push_back({h[i][1], len[i]}); edges[h[i][1]].push_back({h[i][0], len[i]}); } for(int i = 0; i < n; i++) isIn[i] = true; decompose(0, -1); int answer = INF; for(int i = 0; i < n; i++) { sort(distCentroidSubtree[i].begin(), distCentroidSubtree[i].end(), cmp); /*cout << i << " : " << endl; for(int st = 0; st < distCentroidSubtree[i].size(); st++) cout << distCentroidSubtree[i][st].first << ' '; cout << endl;*/ int dr = distCentroidSubtree[i].size() - 1; for(int st = 0; st < distCentroidSubtree[i].size(); st++) { while(dr > st && distCentroidSubtree[i][st].first + distCentroidSubtree[i][dr].first > k) dr--; if(distCentroidSubtree[i][st].first + distCentroidSubtree[i][dr].first == k) answer = min(answer, distCentroidSubtree[i][st].second + distCentroidSubtree[i][dr].second); } } if(answer == INF) answer = -1; return answer; } /*int h[NMAX][2]; int len[NMAX]; int main() { int n, k; cin >> n >> k; for(int i = 0; i < n - 1; i++) cin >> h[i][0] >> h[i][1]; for(int i = 0; i < n - 1; i++) cin >> len[i]; cout << best_path(n, k, h, len); return 0; }*/

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

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:75:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int st = 0; st < distCentroidSubtree[i].size(); st++) {
      |                         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...