제출 #527016

#제출 시각아이디문제언어결과실행 시간메모리
527016Hanksburger경주 (Race) (IOI11_race)C++17
100 / 100
484 ms51756 KiB
#include <bits/stdc++.h> using namespace std; long long dp[1000005], sz[200005], n, k, ans=1e18; vector<pair<long long, long long> > adj[200005], val; vector<long long> val2, tmp; void dfs(long long u, long long prev) { sz[u]=1; for (long long i=0; i<adj[u].size(); i++) { long long v=adj[u][i].first; if (v==prev) continue; dfs(v, u); sz[u]+=sz[v]; } } void dfs2(long long u, long long prev, long long cnt, long long cur) { if (cur>k) return; val.push_back({cnt, cur}); val2.push_back(cur); for (long long i=0; i<adj[u].size(); i++) { long long v=adj[u][i].first, w=adj[u][i].second; if (v==prev) continue; dfs2(v, u, cnt+1, cur+w); } } void dfs3(long long u, long long prev) { tmp.push_back(u); for (long long i=0; i<adj[u].size(); i++) { long long v=adj[u][i].first; if (v==prev) continue; dfs3(v, u); } } void recur(vector<long long> vec) { // cout << "vec: "; // for (long long i=0; i<vec.size(); i++) // cout << vec[i] << ' '; // cout << '\n'; long long m=vec.size(), center; if (m==1) return; dfs(vec[0], -1); for (long long i=0; i<m; i++) { long long u=vec[i]; long long maxi=m-sz[u]; for (long long j=0; j<adj[u].size(); j++) { long long v=adj[u][j].first; if (sz[u]>sz[v]) maxi=max(maxi, sz[v]); } if (maxi<=m/2) { center=u; break; } } // cout << "center: " << center << '\n'; for (long long i=0; i<adj[center].size(); i++) { long long v=adj[center][i].first, w=adj[center][i].second; dfs2(v, center, 1, w); for (long long j=0; j<val.size(); j++) ans=min(ans, dp[k-val[j].second]+val[j].first); for (long long j=0; j<val.size(); j++) dp[val[j].second]=min(dp[val[j].second], val[j].first); // cout << "val: "; // for (long long j=0; j<val.size(); j++) // cout << val[j].first << ' ' << val[j].second << ' '; // cout << '\n'; val.clear(); // cout << "dp: "; // for (long long j=0; j<=k; j++) // cout << dp[j] << ' '; // cout << '\n'; // cout << "ans: " << ans << '\n'; } for (long long i=0; i<val2.size(); i++) dp[val2[i]]=1e18; val2.clear(); for (long long i=0; i<adj[center].size(); i++) { long long v=adj[center][i].first; for (long long j=0; j<adj[v].size(); j++) { if (adj[v][j].first==center) { adj[v].erase(adj[v].begin()+j); break; } } tmp.clear(); dfs3(v, center); recur(tmp); } } int best_path(int N, int K, int H[][2], int L[]) { n=N; k=K; for (long long i=0; i<=n-2; i++) { adj[H[i][0]].push_back({H[i][1], L[i]}); adj[H[i][1]].push_back({H[i][0], L[i]}); } for (long long i=1; i<=k; i++) dp[i]=1e18; for (long long i=0; i<n; i++) tmp.push_back(i); recur(tmp); if (ans==1e18) return -1; return ans; }

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

race.cpp: In function 'void dfs(long long int, long long int)':
race.cpp:9:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |  for (long long i=0; i<adj[u].size(); i++)
      |                      ~^~~~~~~~~~~~~~
race.cpp: In function 'void dfs2(long long int, long long int, long long int, long long int)':
race.cpp:24:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for (long long i=0; i<adj[u].size(); i++)
      |                      ~^~~~~~~~~~~~~~
race.cpp: In function 'void dfs3(long long int, long long int)':
race.cpp:35:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (long long i=0; i<adj[u].size(); i++)
      |                      ~^~~~~~~~~~~~~~
race.cpp: In function 'void recur(std::vector<long long int>)':
race.cpp:57:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for (long long j=0; j<adj[u].size(); j++)
      |                       ~^~~~~~~~~~~~~~
race.cpp:70:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for (long long i=0; i<adj[center].size(); i++)
      |                      ~^~~~~~~~~~~~~~~~~~~
race.cpp:74:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for (long long j=0; j<val.size(); j++)
      |                       ~^~~~~~~~~~~
race.cpp:76:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for (long long j=0; j<val.size(); j++)
      |                       ~^~~~~~~~~~~
race.cpp:89:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for (long long i=0; i<val2.size(); i++)
      |                      ~^~~~~~~~~~~~
race.cpp:92:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for (long long i=0; i<adj[center].size(); i++)
      |                      ~^~~~~~~~~~~~~~~~~~~
race.cpp:95:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   for (long long j=0; j<adj[v].size(); j++)
      |                       ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...