제출 #132969

#제출 시각아이디문제언어결과실행 시간메모리
132969wilwxk경주 (Race) (IOI11_race)C++14
43 / 100
3054 ms37112 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=2e5+5; vector<int> g[MAXN], pes[MAXN]; int n, respf; ll x; class solution { public: int resp=MAXN; void init() { tam[n]=0; memset(prof, 0, sizeof(prof)); solve(0, 1); } void solve(int cur, int k) { basic_scan(cur, cur); cur=find_centroid(cur, cur, tam[cur]); prof[cur]=k; // printf(">> %d <<\n", cur); best.clear(); best[0]={0, 0, n}; for(int i=0; i<g[cur].size(); i++) { int viz=g[cur][i]; ll peso=pes[cur][i]; adv_scan(viz, cur, 1, peso, viz); } for(auto cur : best) { ll d=cur.first; if(best.find(x-d)==best.end()) continue; int a=get<2>(cur.second); int val=get<0>(cur.second); auto outro=best[x-d]; int b=get<2>(outro); int val2= b==a ? get<1>(outro) : get<0>(outro); // printf("d= %lld : %d %d >> %lld + %lld -1\n", d, a, b, val, val2); resp=min(resp, val+val2); } for(auto viz : g[cur]) { if(prof[viz]) continue; solve(viz, k+1); } } private: int tam[MAXN], prof[MAXN]; unordered_map<ll, tuple<int, int, int> > best; void basic_scan(int cur, int p) { tam[cur]=1; for(auto viz : g[cur]) { if(viz==p||prof[viz]) continue; basic_scan(viz, cur); tam[cur]+=tam[viz]; } } void melhora(int cur, ll dd, int d) { if(best.find(dd)==best.end()) { best[dd]={d, MAXN, cur}; return; } int a, b, c; tie(a, b, c)=best[dd]; if(cur==c) best[dd]={min(a, d), b, c}; else if(d<b) best[dd]={a, d, c}; } void adv_scan(int cur, int p, int d, ll dd, int raiz) { if(dd>x) return; melhora(raiz, dd, d); for(int i=0; i<g[cur].size(); i++) { int viz=g[cur][i]; ll peso=pes[cur][i]; if(viz==p||prof[viz]) continue; adv_scan(viz, cur, d+1, dd+peso, raiz); } } int find_centroid(int cur, int p, int val) { int grande=n; for(auto viz : g[cur]) if(viz!=p&&!prof[viz]&&tam[viz]>tam[grande]) grande=viz; if(tam[grande]*2<=val) return cur; return find_centroid(grande, cur, val); } }; int best_path(int N, int K, int H[][2], int L[]) { n=N; x=K; for(int i=0; i<n-1; i++) { int a=H[i][0]; int b=H[i][1]; g[a].push_back(b); pes[a].push_back(L[i]); g[b].push_back(a); pes[b].push_back(L[i]); } solution sol; sol.init(); respf=sol.resp; if(respf>n) respf=-1; return respf; }

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

race.cpp: In member function 'void solution::solve(int, int)':
race.cpp:27:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<g[cur].size(); i++) {
                ~^~~~~~~~~~~~~~
race.cpp: In member function 'void solution::adv_scan(int, int, int, ll, int)':
race.cpp:74:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<g[cur].size(); i++) {
                ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...