Submission #974731

#TimeUsernameProblemLanguageResultExecution timeMemory
974731NemanjaSo2005Sky Walking (IOI19_walk)C++17
0 / 100
1067 ms434632 KiB
#include "walk.h" #include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=2e5+5; ll N,M; struct skywalk{ ll l,r,y; } put[maxn]; struct zgrada{ ll x,y,id; } niz[maxn]; bool cmpsw(skywalk a,skywalk b){ return a.y<b.y; } bool poy(zgrada a,zgrada b){ return a.y<b.y; } int gsz=0; int novi(){ return ++gsz; } set<int> S; vector<pair<int,int>> koji[maxn]; vector<pair<ll,ll>> graf[12*maxn]; bool prosli[12*maxn]; ll dist[12*maxn]; priority_queue<pair<ll,ll>> PQ; void grana(int a,int b,ll w){ graf[a].push_back({b,w}); graf[b].push_back({a,w}); } void Dijkstra(ll gde,ll c){ PQ.push({-c,gde}); while(PQ.size()){ ll tren=PQ.top().second; ll d=-PQ.top().first; PQ.pop(); if(prosli[tren]) continue; prosli[tren]=true; dist[tren]=d; for(auto x:graf[tren]) PQ.push({-d-x.second,x.first}); } } ll min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) { N=x.size(); M=l.size(); for(ll i=0;i<N;i++){ niz[i].x=x[i]; niz[i].y=h[i]; niz[i].id=i; } for(ll i=0;i<M;i++){ put[i].l=l[i]; put[i].r=r[i]; put[i].y=y[i]; } sort(niz,niz+N,poy); sort(put,put+M,cmpsw); ll pok=N-1; for(ll i=M-1;i>=0;i--){ if(pok>=0){ while(niz[pok].y>=put[i].y){ S.insert(niz[pok].id); pok--; if(pok<0) break; } } vector<ll> V; auto it=S.upper_bound(put[i].l-1); for(it;it!=S.end();it++){ if((*it)>put[i].r) break; V.push_back(*it); } int pn=novi(); koji[V[0]].push_back({put[i].y,pn}); for(ll j=1;j<V.size();j++){ ll pr=V[j-1]; ll tr=V[j]; ll d=x[tr]-x[pr]; int nn=novi(); grana(pn,nn,d); koji[V[j]].push_back({put[i].y,nn}); pn=nn; } } for(ll i=0;i<N;i++){ for(ll j=1;j<koji[i].size();j++){ ll d=abs(koji[i][j].first-koji[i][j-1].first); ll a=koji[i][j].second; ll b=koji[i][j-1].second; grana(a,b,d); } } int last=novi(); grana(last,koji[g].back().second,koji[g].back().first); int first=novi(); grana(first,koji[s].back().second,koji[s].back().first); dist[last]=-1; Dijkstra(first,0); /* for(int i=1;i<=gsz;i++) cout<<dist[i]<<" "; cout<<endl; */ ll res=dist[last]; return res; }

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:76:11: warning: statement has no effect [-Wunused-value]
   76 |       for(it;it!=S.end();it++){
      |           ^~
walk.cpp:85:19: 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]
   85 |       for(ll j=1;j<V.size();j++){
      |                  ~^~~~~~~~~
walk.cpp:98:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |       for(ll j=1;j<koji[i].size();j++){
      |                  ~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...