제출 #41094

#제출 시각아이디문제언어결과실행 시간메모리
41094comtalyst경주 (Race) (IOI11_race)C++14
9 / 100
169 ms26748 KiB
/* * Task: ioi11_race * Lang: C/C++11 * Site: oj.uz * Last Update: 12/2/2018 */ #include <bits/stdc++.h> //#pragma GCC optimize ("O3") using namespace std; /* Note ---------------------------- Learned : Bugs found & solved : Optimizations : ---------------------------- */ #define x first #define y second #define umap unordered_map #define pqueue priority_queue #define mset multiset #define mp make_pair #define mt make_tuple #define long long long #define MOD 1000000007 #define MAX (long)(1e16+5) #define MIN (long)(-1e16-5) #define FILEIN_ freopen("__in.txt","r",stdin) #define FILEOUT_ freopen("__out.txt","w",stdout) #define FILEIN(text) freopen(text,"r",stdin) #define FILEOUT(text) freopen(text,"w",stdout) //int tmp[200005][2],tmp2[200005]; vector<pair<long,long>> adl[200005]; umap<long,long> s[200005]; long ls[200005],sid[200005],lv[200005],sc,n,m,mn=MAX; void solve(long x,long f){ long i,y,id,v,need,w; pair<long,long> mx={0,0}; umap<long,long>::iterator it; lv[x] = lv[f]+1; for(i = 0; i < adl[x].size(); i++){ y = adl[x][i].x; if(y == f) continue; solve(y,x); id = sid[y]; mx = max(mx,{(long)s[id].size(),y}); } if(mx.x){ sid[x] = sid[mx.y]; } else{ sid[x] = ++sc; mx.y = 0; } for(i = 0; i < adl[x].size(); i++){ y = adl[x][i].x; if(y == f || y == mx.y) continue; id = sid[y]; it = s[id].begin(); while(it != s[id].end()){ v = (*it).x + ls[id]; need = m-v-ls[sid[x]]; if(s[sid[x]][need]){ mn = min(mn,s[sid[x]][need]+(*it).y-lv[x]*2); } else{ s[sid[x]].erase(need); } it++; } while(!s[id].empty()){ if(s[sid[x]][v-ls[sid[x]]]){ s[sid[x]][v-ls[sid[x]]] = min(s[sid[x]][v-ls[sid[x]]],(*s[id].begin()).y); } else{ s[sid[x]][v-ls[sid[x]]] = (*s[id].begin()).y; } s[id].erase(s[id].begin()); } } for(i = 0; i < adl[x].size(); i++){ y = adl[x][i].x; w = adl[x][i].y; if(y == f){ break; } } need = m-w-ls[sid[x]]; if(s[sid[x]][need]){ mn = min(mn,s[sid[x]][need]-lv[f]); } else{ s[sid[x]].erase(need); } ls[sid[x]] += w; s[sid[x]][w - ls[sid[x]]] = lv[x]; } long best_path(int _n,int _m,int _edl[][2],int _edw[]){ // f*ck you 0-based idx long i,j; n = _n; m = _m; for(i = 0; i < n-1; i++){ adl[_edl[i][0]+1].emplace_back(_edl[i][1]+1,_edw[i]); adl[_edl[i][1]+1].emplace_back(_edl[i][0]+1,_edw[i]); if(_edw[i] == m){ return 1; } } solve(1,0); if(mn != MAX){ return mn; } else{ return -1; } } /*main(){ int t,i,j,k,_n,_m; FILEIN_; scanf("%d %d",&_n,&_m); for(i = 0; i < _n-1; i++){ scanf("%d %d %d",&tmp[i][0],&tmp[i][1],&tmp2[i]); } printf(">> %lld\n",best_path(_n,_m,tmp,tmp2)); return 0; }*/

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

race.cpp: In function 'void solve(long long int, long long int)':
race.cpp:46:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < adl[x].size(); i++){
             ~~^~~~~~~~~~~~~~~
race.cpp:60:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < adl[x].size(); i++){
             ~~^~~~~~~~~~~~~~~
race.cpp:86:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < adl[x].size(); i++){
             ~~^~~~~~~~~~~~~~~
race.cpp: In function 'long long int best_path(int, int, int (*)[2], int*)':
race.cpp:105:9: warning: unused variable 'j' [-Wunused-variable]
  long i,j;
         ^
race.cpp: In function 'void solve(long long int, long long int)':
race.cpp:93:10: warning: 'w' may be used uninitialized in this function [-Wmaybe-uninitialized]
  need = m-w-ls[sid[x]];
         ~^~
race.cpp:77:18: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
    if(s[sid[x]][v-ls[sid[x]]]){
                 ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...