제출 #706471

#제출 시각아이디문제언어결과실행 시간메모리
706471Asamai경주 (Race) (IOI11_race)C++17
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;} template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;} #define all(a) a.begin(), a.end() #define pb push_back #define pf push_front #define fi first #define se second //#define int long long typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ld; typedef pair<db, db> pdb; typedef pair<ld, ld> pld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<ll, int> plli; typedef pair<int, ll> pill; const int MAX_N = 2e5 + 5; const int mod = 1e9 + 7; // 998244353 const int inf = 1e9 + 1; int n, k; vector<pii> adj[MAX_N]; bool processed[MAX_N]; int ans = inf; int child[MAX_N]; int dfs(int u, int pr = 0) { child[u] = 1; for (auto it : adj[u]) { int v = it.fi; if (!processed[v] && v != pr) { child[u] += dfs(v, u); } } return child[u]; } int find_centroid(int u, int pr, int sz) { for (auto it : adj[u]) { int v = it.fi; if (!processed[v] && v != pr && child[v] > sz) { return find_centroid(v, u, sz); } } return u; } const int MAX_VAL = 1e6 + 10; int dp[MAX_VAL]; vector<int> used; void go_cal(int u, int pr, bool ok, int len, int dep) { if (k < len) return; if (ok) { used.pb(len); minimize(dp[len], dep); } else { minimize(ans, dp[k - len] + dep); } for (auto it : adj[u]) { int v = it.fi; int w = it.se; if (!processed[v] && v != pr) { go_cal(v, u, ok, len + w, dep + 1); } } } void centroid_decomposition(int u) { int c = find_centroid(u, 0, dfs(u) >> 1); processed[c] = true; used.clear(); dp[0] = 0; for (auto it : adj[c]) { int v = it.fi; int w = it.se; if (!processed[v]) { go_cal(v, c, false, w, 1); go_cal(v, c, true, w, 1); } } for (auto it : used) { dp[it] = inf; } for (auto it : adj[c]) { int v = it.fi; if (!processed[v]) { centroid_decomposition(v); } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k; for (int i = 0; i <= k; i ++) { dp[i] = inf; } for (int i = 1; i < n; i++) { int u, v, w; cin >> u >> v >> w; u++; v++; adj[u].pb({v, w}); adj[v].pb({u, w}); } centroid_decomposition(1); cout << (ans == inf ? -1 : ans); return 0; } /* */

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

/usr/bin/ld: /tmp/ccehc9pE.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccYNsxRB.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccYNsxRB.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status