Submission #132947

#TimeUsernameProblemLanguageResultExecution timeMemory
132947wilwxkRace (IOI11_race)C++14
0 / 100
13 ms10616 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(); 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; int a=get<2>(cur.second); int val=get<0>(cur.second); if(best.find(x-d)==best.end()) continue; 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]; 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}; // printf("best[%lld]= {%d, %d, %d}\n", dd, d, MAXN, cur); return; } int a, b, c; tie(a, b, c)=best[dd]; if(d<=a) best[dd]={d, a, cur}; else if(d<b) best[dd]={a, d, c}; } void adv_scan(int cur, int p, int d, ll dd, int raiz) { // printf("%d %d %d %lld - %d\n", cur, p, d, dd, raiz); 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; }

Compilation message (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:75: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...