Submission #729530

#TimeUsernameProblemLanguageResultExecution timeMemory
729530NemanjaSo2005Race (IOI11_race)C++14
43 / 100
469 ms36168 KiB
#include "race.h" #include<bits/stdc++.h> #define ll long long using namespace std; struct grana{ ll gde; ll cena; }pp; vector<grana> stablo[200005]; bool zan; ll N,K,res=1e9; const ll INF=1e9; ll kol[200005],najb[1000005],p1,p2; ll duzina[200005],puta[200005]; bool block[200005]; ll rootuj(ll gde,ll pret){ if(block[gde]) return 0; kol[gde]=1; for(ll i=0;i<stablo[gde].size();i++) if(stablo[gde][i].gde!=pret) kol[gde]+=rootuj(stablo[gde][i].gde,gde); return kol[gde]; } ll nadji(ll gde,ll pret,ll pola){ //if(zan) // cout<<gde<<" "<<pret<<endl; ll sled=-1; for(ll i=0;i<stablo[gde].size();i++){ if(block[stablo[gde][i].gde] or stablo[gde][i].gde==pret) continue; if(kol[stablo[gde][i].gde]>pola) sled=stablo[gde][i].gde; } if(sled==-1) return gde; return nadji(sled,gde,pola); } vector<ll> V; void racunaj(ll gde,ll pret,ll dist,ll put){ duzina[gde]=dist; puta[gde]=put; // cout<<"DFS "<<gde<<" "<<pret<<" "<<put<<" "<<dist<<endl; if(dist<=K) res=min(res,put+najb[K-dist]); if(dist==K) res=min(res,put); V.push_back(gde); for(ll i=0;i<stablo[gde].size();i++){ if(block[stablo[gde][i].gde] or stablo[gde][i].gde==pret) continue; racunaj(stablo[gde][i].gde,gde,dist+stablo[gde][i].cena,put+1); } if(dist<=K) najb[dist]=min(najb[dist],put); return; } void rek(ll gde){ // cout<<"REK NA "<<gde<<endl; // zan=(gde==19); rootuj(gde,gde); ll c=nadji(gde,gde,kol[gde]/2+3); V.clear(); racunaj(c,c,0,0); // cout<<"CENTROID JE "<<c<<endl; /* for(ll i=0;i<V.size();i++) cout<<V[i]<<": "<<puta[V[i]]<<" "<<duzina[V[i]]<<endl; cout<<endl; cout<<"RES= "<<res<<endl; */ for(ll i=0;i<V.size();i++){ if(duzina[V[i]]>K) continue; najb[duzina[V[i]]]=INF; } block[c]=true; kol[c]=INF; for(ll i=0;i<stablo[c].size();i++) if(!block[stablo[c][i].gde]) rek(stablo[c][i].gde); return; } int best_path(int n,int k,int h[][2],int l[]){ N=n; K=k; for(ll i=0;i<N-1;i++){ h[i][0]++; h[i][1]++; pp.cena=l[i]; pp.gde=h[i][1]; stablo[h[i][0]].push_back(pp); //cout<<h[i][0]<<" "<<h[i][1]<<endl; pp.gde=h[i][0]; stablo[h[i][1]].push_back(pp); } for(ll i=0;i<=K;i++) najb[i]=INF; rek(1); if(res==1e9) return -1; return res; }

Compilation message (stderr)

race.cpp: In function 'long long int rootuj(long long int, long long int)':
race.cpp:20:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |    for(ll i=0;i<stablo[gde].size();i++)
      |               ~^~~~~~~~~~~~~~~~~~~
race.cpp: In function 'long long int nadji(long long int, long long int, long long int)':
race.cpp:29:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |    for(ll i=0;i<stablo[gde].size();i++){
      |               ~^~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void racunaj(long long int, long long int, long long int, long long int)':
race.cpp:49:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |    for(ll i=0;i<stablo[gde].size();i++){
      |               ~^~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void rek(long long int)':
race.cpp:72:16: 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]
   72 |    for(ll i=0;i<V.size();i++){
      |               ~^~~~~~~~~
race.cpp:79:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<grana>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |    for(ll i=0;i<stablo[c].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...