제출 #849287

#제출 시각아이디문제언어결과실행 시간메모리
849287manhtuan22007경주 (Race) (IOI11_race)C++14
21 / 100
73 ms176464 KiB
#include<bits/stdc++.h> using namespace std; #define name "race" #define ll long long //#define int long long int n , k; vector<vector<pair<int , int>>> g(200010); namespace sub12{ const int maxn = 1e3 + 10; int par[maxn][11] , h[maxn] , cost[maxn]; void dfs(int u){ for(auto e : g[u]){ int v = e.first; if(v == par[u][0]) continue; h[v] = h[u] + 1; cost[v] = cost[u] + e.second; par[v][0] = u; for(int i = 1 ; i < 11 ; i ++){ par[v][i] = par[par[v][i - 1]][i - 1]; } dfs(v); } } int lca(int u , int v){ if(h[u] < h[v]) swap(u , v); int k = h[u] - h[v]; for(int i = 0 ; (1 << i) <= k ; i ++){ if(k >> i & 1) u = par[u][i]; } if(u == v) return u; for(int i = 10 ; i >= 0 ; i --){ if(par[u][i] != par[v][i]){ u = par[u][i] , v = par[v][i]; } } return par[u][0]; } int solve(int n , int k){ dfs(1); int res = -1; for(int i = 1 ; i <= n ; i ++) for(int j = i + 1 ; j <= n ; j ++){ int p = lca(i , j); int d = cost[i] + cost[j] - 2 * cost[p]; int num = h[i] + h[j] - 2 * h[p]; if(d == k) res = (res == -1 ? num : min(res , num)); } return res; } } namespace sub3{ const int maxn = 2e5 + 10; int dp[maxn][205] , k; void dfs(int u , int p){ dp[u][0] = 0; for(auto e : g[u]){ int v = e.first; if(v == p) continue; dfs(v , u); for(int i = 0 ; i <= k ; i ++){ if(i + e.second <= k) dp[u][i + e.second] = min(dp[u][i + e.second] , dp[v][i] + 1); } } } int solve(int n , int k){ k = k; memset(dp , 0x3f , sizeof dp); int inf = dp[0][0]; dfs(1 , 0); int res = -1; for(int i = 1 ; i <= n ; i ++){ if(dp[i][k] == inf) continue; res = (res == -1 ? dp[i][k] : min(res , dp[i][k])); } return res; } } int best_path(int n , int k , int h[][2] , int l[]){ for(int i = 0 ; i < n - 1 ; i ++){ int u = h[i][0] , v = h[i][1]; ++u , ++v; g[u].push_back({v , l[i]}); g[v].push_back({u , l[i]}); } if(n <= 1000) return sub12::solve(n , k); else if(k <= 100) return sub3::solve(n , k); } // int main(){ // int n , k; // cin >> n>> k; // int h[20][2] , l[20]; // for(int i = 0 ; i < n - 1 ; i ++){ // cin >> h[i][0] >> h[i][1] >> l[i]; // } // cout << best_path(n , k , h , l); // } //

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

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:100:1: warning: control reaches end of non-void function [-Wreturn-type]
  100 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...