제출 #755114

#제출 시각아이디문제언어결과실행 시간메모리
755114amin경주 (Race) (IOI11_race)C++14
9 / 100
210 ms26268 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #define ll long long map<ll,ll>ma[200000]; ll pa[200000]; ll dist[200000]; ll k; ll val[200000]; ll sz[200000]; ll ans=1000000; ll par(ll x) { if(pa[x]==x) return x; pa[x]=par(pa[x]); return pa[x]; } ll un(ll x,ll y,ll desired) { ll sum=1000000; x=par(x); y=par(y); if(x==y) return sum; if(sz[y]>sz[x]) swap(x,y); pa[y]=x; sz[x]+=sz[y]; sz[y]=0; // cout<<sz[x]<<endl; for(auto i:ma[y]) { // cout<<desired-i.first<<endl; if(ma[x][desired-i.first]!=0)//beware of the root case { // cout<<1<<endl; sum=min(sum,i.second+ma[x][desired-i.first]); } }for(auto i:ma[y]) { if(ma[x][i.first]==0) ma[x][i.first]=i.second; else ma[x][i.first]=min(i.second,ma[x][i.first]); } ma[y].clear(); return sum; } vector<ll>v[100000],w[100000]; void dfs(ll in,ll pa) { for(ll y=0;y<v[in].size();y++) { ll i=v[in][y]; ll h=w[in][y]; if(i==pa) continue; dist[i]=dist[in]+1; val[i]=val[in]+h; dfs(i,in); } } void solve(ll in,ll pa) { ma[in][val[in]]=dist[in]; // cout<<dist[in]<<endl; ll z=1000000; for(auto i:v[in]) { if(i==pa) continue; solve(i,in); z=min(z,un(in,i,k+2*(val[in]))); } // cout<<in<<' '<<z<<endl; ans=min(ans,z-2*dist[in]); } int best_path(int N, int K, int H[][2], int L[]) { ll n=N; k=K; for(ll i=0;i<n;i++) { ll x=H[i][0]; ll y=H[i][1]; v[x].push_back(y); v[y].push_back(x); w[x].push_back(L[i]); w[y].push_back(L[i]); } dist[0]=1; dfs(0,0); for(ll i=0;i<n;i++) { pa[i]=i; sz[i]=1; } solve(0,0);/* for(ll i=0;i<n;i++) { // cout<<ma[i].size()<<' '<<sz[i]; for(auto z:ma[i]) { cout<<z.first<<' '<<z.second<<endl; } }*/ /*cout<<endl; cout<<ans<<endl;*/ if(ans>n) return -1; else return ans; }

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

race.cpp: In function 'long long int un(long long int, long long int, long long int)':
race.cpp:26:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   26 |     if(sz[y]>sz[x])
      |     ^~
race.cpp:28:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   28 |         pa[y]=x;
      |         ^~
race.cpp: In function 'void dfs(long long int, long long int)':
race.cpp:57:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(ll y=0;y<v[in].size();y++)
      |                ~^~~~~~~~~~~~~
race.cpp:61:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   61 |         if(i==pa)
      |         ^~
race.cpp:63:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   63 |             dist[i]=dist[in]+1;
      |             ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...