Submission #507479

#TimeUsernameProblemLanguageResultExecution timeMemory
507479haxormanRace (IOI11_race)C++14
0 / 100
3 ms5068 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; const int mxN = 2e5 + 7; int n, k; vector<int> cur_seg; vector<pair<int,int>> sums, graph[mxN]; int dp[mxN], p[mxN]; unordered_map<int,int> len; bool vis[mxN]; void dfs(int u, int par) { dp[u] = 1; p[u] = par; for (auto pr : graph[u]) { int v = pr.first; if (!vis[v] && v != par) { dfs(v, u); dp[u] += dp[v]; } } cur_seg.push_back(u); } int find_centroid(int x) { cur_seg.clear(); dfs(x, -1); for (int u : cur_seg) { int max_subtree = cur_seg.size() - dp[u]; for (auto pr : graph[u]) { int v = pr.first; if (v != p[u] && !vis[v]) { max_subtree = max(max_subtree, dp[v]); } } if (max_subtree <= cur_seg.size() / 2) { return u; } } return x; } int ans = INT_MAX; void find_min_path(int u, int par, int cnt, int sum) { if (sum < k && len[k - sum]) { ans = min(ans, cnt + len[k - sum]); } else if (sum == k) { ans = min(ans, cnt); } for (auto pr : graph[u]) { int v = pr.first, w = pr.second; if (!vis[v] && v != par) { find_min_path(v, u, cnt + 1, sum + w); } } sums.push_back({sum, cnt}); } void decompose(int x) { int c = find_centroid(x); vis[c] = true; len.clear(); for (auto pr : graph[c]) { int v = pr.first, w = pr.second; if (!vis[v]) { sums.clear(); find_min_path(v, c, 1, w); for (auto prr : sums) { int sum = prr.first, cnt = prr.second; if (!len[sum]) { len[sum] = cnt; } else { len[sum] = min(len[sum], cnt); } } } } for (auto pr : graph[c]) { int v = pr.first; if (!vis[v]) { decompose(v); } } } 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 u = H[i][0], v = H[i][1], w = L[i]; graph[u].push_back({v, w}); graph[v].push_back({u, w}); } decompose(0); return ans; }

Compilation message (stderr)

race.cpp: In function 'int find_centroid(int)':
race.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   if (max_subtree <= cur_seg.size() / 2) {
      |       ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...