제출 #833781

#제출 시각아이디문제언어결과실행 시간메모리
833781algorithm16경주 (Race) (IOI11_race)C++14
43 / 100
244 ms60396 KiB
#include<iostream> #include<vector> #include<set> #include<algorithm> #include "race.h" using namespace std; typedef long long int llint; vector <pair<int,int> > v[200005]; set <pair<llint,llint> > s[200005]; llint k1,mn=1e9; void f(int x,int y,llint dd,llint ll) { if(s[x].size()<s[y].size()) swap(s[x],s[y]); for(set <pair<llint,llint> >::iterator it=s[y].begin();it!=s[y].end();) { llint l=(*it).first,d=(*it).second; l-=ll; d-=dd; set <pair<llint,llint> >::iterator it2=s[x].lower_bound(make_pair(k1-l+ll,-1)); if(it2!=s[x].end() && (*it2).first==k1-l+ll) mn=min(mn,d+(*it2).second-dd); it2=s[x].lower_bound(make_pair(l+ll,-1)); if(it2==s[x].end() || (*it2).first!=l+ll) s[x].insert((*it)); else if((*it2).second>(*it).second) { s[x].erase(it2); s[x].insert((*it)); } it=s[y].erase(it); } } void dfs(int x,int p,llint d,llint l) { s[x].insert(make_pair(l,d)); for(int i=0;i<v[x].size();i++) { if(v[x][i].first==p) continue; dfs(v[x][i].first,x,d+1,l+v[x][i].second); f(x,v[x][i].first,d,l); } } int best_path(int n,int k,int h[][2],int l[]) { k1=k; for(int i=0;i<n-1;i++) { 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])); } dfs(0,0,0,0); if(mn==1e9) mn=-1; return mn; } /*int main() { int n,k; cin >> n >> k; for(int i=0;i<n-1;i++) { int a,b,l1; cin >> a >> b >> l1; h[i][0]=a; h[i][1]=b; l[i]=l1; } cout << best_path(n,k); } */

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

race.cpp: In function 'void dfs(int, int, llint, llint)':
race.cpp:30:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i=0;i<v[x].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...