Submission #1115064

#TimeUsernameProblemLanguageResultExecution timeMemory
1115064gustavo_dRace (IOI11_race)C++17
Compilation error
0 ms0 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") const int MAXN = 2e5; const int MAXV = 1e6+1; vector<pair<int, int>> adj[MAXN]; bool vis[MAXN]; int sz[MAXN]; bool in[MAXN]; int n, k; void dfs(int v, int pai) { sz[v] = 1; for (auto& [viz, w] : adj[v]) { if (viz == pai or in[viz]) continue; dfs(viz); sz[v] += sz[viz]; } } int find_centroid(int v, int pai, int qty) { // cout << "buscando centroid " << v << endl; for (auto& [viz, w] : adj[v]) { if (viz == pai or in[viz]) continue; if (sz[viz] > qty / 2) find_centroid(viz, v, qty); } // cout << "é" << v <<endl; return v; } vector<int> sub_mn_depth(MAXV, 1e8); vector<pair<int, int>> dists[MAXV]; vector<int> sub_dists; void get_dist(int v, int pai, int dist, int depth) { if (dist > k) return; sub_mn_depth[dist] = min(sub_mn_depth[dist], depth); sub_dists.push_back(dist); for (auto& [viz, w] : adj[v]) { if (viz == pai or in[viz]) continue; get_dist(viz, v, dist + w, depth+1); } } int ans = 1e8; void decomp(int v, int qty) { dfs(v); int centroid = find_centroid(v, -1, sz[v]); in[centroid] = true; vector<int> all_dists; // if (centroid == 8) cout << centroid << " é centroid decompondo" << v << endl; for (auto& [viz, w] : adj[centroid]) { if (in[viz]) continue; get_dist(viz, centroid, w, 1); for (int d : sub_dists) { dists[d].push_back({sub_mn_depth[d], viz}); sub_mn_depth[d] = 1e8; all_dists.push_back(d); } sub_dists.clear(); } for (int d : all_dists) { sort(dists[d].begin(), dists[d].end()); } if (!dists[k].empty()) ans = min(ans, dists[k][0].first); for (auto& [viz, w] : adj[centroid]) { if (in[viz]) continue; get_dist(viz, centroid, w, 1); for (int d : sub_dists) { for (int i=0; d <= k and i<min(2, (int)dists[k-d].size()); i++) { if (dists[k-d][i].second == viz) continue; ans = min(ans, dists[k-d][i].first + sub_mn_depth[d]); } sub_mn_depth[d] = 1e8; } sub_dists.clear(); } for (int d : all_dists) dists[d].clear(); for (auto& [viz, w] : adj[centroid]) { if (in[viz]) continue; decomp(viz); } } 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]; int w = L[i]; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } dfs(0); decomp(0, n); return (ans == (int)1e8 ? -1 : ans); }

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:19:16: error: too few arguments to function 'void dfs(int, int)'
   19 |         dfs(viz);
      |                ^
race.cpp:15:6: note: declared here
   15 | void dfs(int v, int pai) {
      |      ^~~
race.cpp: In function 'void decomp(int, int)':
race.cpp:49:10: error: too few arguments to function 'void dfs(int, int)'
   49 |     dfs(v);
      |          ^
race.cpp:15:6: note: declared here
   15 | void dfs(int v, int pai) {
      |      ^~~
race.cpp:83:19: error: too few arguments to function 'void decomp(int, int)'
   83 |         decomp(viz);
      |                   ^
race.cpp:48:6: note: declared here
   48 | void decomp(int v, int qty) {
      |      ^~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:96:10: error: too few arguments to function 'void dfs(int, int)'
   96 |     dfs(0);
      |          ^
race.cpp:15:6: note: declared here
   15 | void dfs(int v, int pai) {
      |      ^~~