제출 #238619

#제출 시각아이디문제언어결과실행 시간메모리
238619Ruxandra985경주 (Race) (IOI11_race)C++14
100 / 100
460 ms93176 KiB
#include <bits/stdc++.h> #include "race.h" #define DIMN 200010 #define MAX_N 500000 using namespace std; vector < pair <int,int> > v[DIMN]; set < pair <long long,int> > per[DIMN]; int sub[DIMN] , f[DIMN] , distanta[DIMN]; long long add[DIMN]; int sol; void precalc (int nod , int tt){ int i , vecin; sub[nod] = 1; for (i = 0 ; i < v[nod].size() ; i++){ vecin = v[nod][i].first; if (vecin != tt && !f[vecin]){ precalc (vecin , nod); sub[nod] += sub[vecin]; } } } void dfs (int nod , int tt , int k){ int i , vecin , maxi = 0 , fiu ; long long rms; set < pair <long long,int> > :: iterator aux; for (i = 0 ; i < v[nod].size() ; i++){ vecin = v[nod][i].first; if (vecin != tt && sub[vecin] > maxi){ maxi = sub[vecin]; fiu = vecin; } } for (i = 0 ; i < v[nod].size() ; i++){ vecin = v[nod][i].first; if (vecin != tt){ dfs (vecin , nod , k); add[vecin] += v[nod][i].second; distanta[vecin]++; } } if (maxi){ per[nod].swap(per[fiu]); add[nod] = add[fiu]; distanta[nod] = distanta[fiu]; for (i = 0 ; i < v[nod].size() ; i++){ vecin = v[nod][i].first; if (vecin != tt){ if (vecin != fiu){ rms = k - v[nod][i].second - add[nod]; aux = per[nod].upper_bound(make_pair(rms , -2000000000)); if (aux != per[nod].end() && aux->first == rms){ sol = min(sol , 1 + aux->second + distanta[nod]); } } per[nod].insert(make_pair(v[nod][i].second - add[nod] , 1 - distanta[nod])); } if (vecin != tt && vecin != fiu){ /// sa zicem ca nod ar fi lca - ul , un capat pana acum , unul in vecin for (set <pair <long long,int> > :: iterator it = per[vecin].begin() ; it != per[vecin].end() ; it++){ if (it->first + add[vecin] > k) continue; rms = k - (it->first + add[vecin]) - add[nod]; aux = per[nod].upper_bound(make_pair(rms , -2000000000)); if (aux != per[nod].end() && aux->first == rms){ sol = min(sol , it->second + distanta[vecin] + aux->second + distanta[nod]); } } /// vezi cum le unesti for (set <pair <long long,int> > :: iterator it = per[vecin].begin() ; it != per[vecin].end() ; it++){ if (it->first + add[vecin] > k) continue; /// nu imi pasa per[nod].insert(make_pair(it->first + add[vecin] - add[nod] , it->second + distanta[vecin] - distanta[nod])); } } } } aux = per[nod].upper_bound(make_pair(k - add[nod] , -2000000000)); if (aux != per[nod].end() && aux->first == k - add[nod]){ sol = min(sol , aux->second + distanta[nod]); } } int best_path(int n, int k, int h[][2], int l[]){ int i; for (i = 0 ; i < n - 1 ; i++){ h[i][1]++; h[i][0]++; v[h[i][0]].push_back(make_pair(h[i][1] , l[i])); v[h[i][1]].push_back(make_pair(h[i][0] , l[i])); } precalc (1 , 0); sol = 2000000000; dfs (1 , 0 , k); return (sol == 2000000000 ? -1 : sol); }

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

race.cpp: In function 'void precalc(int, int)':
race.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < v[nod].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int)':
race.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < v[nod].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
race.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < v[nod].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
race.cpp:57:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < v[nod].size() ; i++){
                      ~~^~~~~~~~~~~~~~~
race.cpp:28:32: warning: 'fiu' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int i , vecin , maxi = 0 , fiu ;
                                ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...