제출 #977203

#제출 시각아이디문제언어결과실행 시간메모리
977203saayan007경주 (Race) (IOI11_race)C++17
0 / 100
2 ms11612 KiB
#include "race.h" #include "bits/stdc++.h" using namespace std; #warning notusing64bitintegers #define rep(i, a, b) for(int i = (a); i <= (b); ++i) #define repd(i, a, b) for(int i = (a); i >= (b); --i) #define em emplace #define eb emplace_back const int mxN = 2e5L + 10; const int mxK = 1e6L + 10; int n, k; vector<pair<int, int>> adj[mxN]; int ans = mxN; int sz[mxN]; bool proc[mxN] = {}; int dp[mxK]; int get_sz(int x, int p) { sz[x] = 1; for(auto [y, w] : adj[x]) { if(proc[y] || y == p) continue; sz[x] += get_sz(y, x); } return sz[x]; } int get_cen(int x, int p, int tot) { for(auto [y, w] : adj[x]) { if(proc[y] || y == p || sz[y] * 2 <= tot) continue; return get_cen(y, x, tot); } return x; } void dfs(int x, int p, int dep, int dis, bool flag) { if(dis > k) return; if(flag == 0) { if(dp[k - dis] != mxN) ans = min(ans, dep + dp[k - dis]); } else if(flag == 1) { dp[dis] = min(dp[dis], dep); } else { dp[dis] = mxN; } for(auto [y, w] : adj[x]) { if(proc[y] || y == p) continue; dfs(y, x, dep + 1, dis + w, flag); } } void solve(int x = 1, int p = -1) { int c = get_cen(x, p, get_sz(x, p)); dp[0] = 0; for(auto [d, w] : adj[c]) { if(proc[d]) continue; dfs(d, c, 1, w, 0); dfs(d, c, 1, w, 1); dfs(d, c, 1, w, 2); } dp[0] = mxN; proc[c] = 1; for(auto [d, w] : adj[c]) { if(proc[d]) continue; solve(d, c); } } int best_path(int N, int K, int H[][2], int L[]) { rep(i, 0, K) dp[i] = mxN; n = N; k = K; rep(i, 0, n - 2) { adj[H[i][0] + 1].eb(H[i][1] + 1, L[i]); adj[H[i][1] + 1].eb(H[i][0] + 1, L[i]); } solve(); return (ans > n - 1 ? -1 : ans); }

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

race.cpp:4:2: warning: #warning notusing64bitintegers [-Wcpp]
    4 | #warning notusing64bitintegers
      |  ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...