제출 #272940

#제출 시각아이디문제언어결과실행 시간메모리
272940hhh07경주 (Race) (IOI11_race)C++14
0 / 100
4 ms4992 KiB
#include <iostream> #include <vector> #include <set> #include <queue> #include <cstring> #include <climits> #include <algorithm> using namespace std; typedef pair<int, int> ii; typedef long long ll; typedef vector<int> vi; typedef vector<ii> vii; int K, N, res, curr_maks, curr_node, cnt, ans; vector<vii> adjList(200001); vi subtree, gotov, mini, moze; void cal_subtree(int curr, int prev){ int D = 0; for (int i = 0; i < adjList[curr].size(); i++){ int t = adjList[curr][i].first; if (t != prev && !gotov[t]){ cal_subtree(t, curr); D += 1 + subtree[t]; } } subtree[curr] = D; } void find_centr(int curr, int prev, int uk){ int x = uk - subtree[curr] - 1; for (int i = 0; i < adjList[curr].size(); i++){ int t = adjList[curr][i].first; if (t != prev && !gotov[t]){ find_centr(t, curr, uk); x = max(x, 1 + subtree[t]); } } if (curr_maks > x){ curr_node = curr; curr_maks = x; } } void dfs1(int curr, int prev, int dist, int depth){ if (dist > K) return; if (moze[dist] != cnt || depth < mini[dist]){ moze[dist] = cnt; mini[dist] = depth; } for (int i = 0; i < adjList[curr].size(); i++){ int t = adjList[curr][i].first; if (t != prev && !gotov[t]) dfs1(t, curr, dist + adjList[curr][i].second, depth + 1); } } void dfs2(int curr, int prev, int dist, int depth){ if (dist > K) return; //cout << curr << " " << prev << " " << dist << endl; if (moze[K - dist] == cnt){ ans = min(ans, depth + mini[K - dist]); //cout << curr << " " << prev << " " << dist << endl; } if (K == dist){ ans = min(ans, depth); //cout << curr << " " << prev << " " << dist << endl; } for (int i = 0; i < adjList[curr].size(); i++){ int t = adjList[curr][i].first; if (t != prev && !gotov[t]) dfs2(t, curr, dist + adjList[curr][i].second, depth + 1); } } void solve(int curr){ cal_subtree(curr, -1); if (subtree[curr] <= 1) return; curr_node = -1; curr_maks = INT_MAX; find_centr(curr, -1, subtree[curr] + 1); int centr = curr_node; cout << centr << endl; cnt++; for (int i = 0; i < adjList[centr].size(); i++){ int t = adjList[centr][i].first; if (!gotov[t]){ dfs2(t, centr, adjList[centr][i].second, 1); dfs1(t, centr, adjList[centr][i].second, 1); } } //1. i 2. dfs gotov[centr] = true; for (int i = 0; i < adjList[centr].size(); i++){ int t = adjList[centr][i].first; if (!gotov[t]) solve(t); } } int best_path(int n, int k, int h[][2], int l[]){ res = INT_MAX; N = n; K = k; for (int i = 0; i < n - 1; i++){ adjList[h[i][0]].push_back({h[i][1], l[i]}); adjList[h[i][1]].push_back({h[i][0], l[i]}); } gotov.assign(n, false); mini.assign(n, 0); subtree.assign(n, 0); moze.assign(n, -1); cnt = 0; ans = INT_MAX; solve(0); if (ans == INT_MAX) return -1; return ans; }

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

race.cpp: In function 'void cal_subtree(int, int)':
race.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < adjList[curr].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void find_centr(int, int, int)':
race.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int i = 0; i < adjList[curr].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void dfs1(int, int, int, int)':
race.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for (int i = 0; i < adjList[curr].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void dfs2(int, int, int, int)':
race.cpp:68:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   68 |   if (dist > K)
      |   ^~
race.cpp:71:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   71 |     if (moze[K - dist] == cnt){
      |     ^~
race.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for (int i = 0; i < adjList[curr].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:97:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for (int i = 0; i < adjList[centr].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~
race.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for (int i = 0; i < adjList[centr].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...