Submission #974715

#	Time	Username	Problem	Language	Result	Execution time	Memory
974715		NemanjaSo2005	Sky Walking (IOI19_walk)	C++17	0 / 100	618 ms	118308 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
const int mostll=11;
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;
}
bool pox(zgrada a,zgrada b){
   return a.x<b.x;
}
set<ll> S;
vector<pair<ll,ll>> graf[12*maxn];
vector<ll> presek[maxn];
bool prosli[12*maxn];
ll dist[12*maxn];
priority_queue<pair<ll,ll>> PQ;
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) {
   s++;
   g++;

	N=x.size();
	M=l.size();
	for(ll i=1;i<=N;i++){
      niz[i].x=x[i-1];
      niz[i].y=h[i-1];
      niz[i].id=i;
	}
	for(ll i=1;i<=M;i++){
      put[i].l=l[i-1]+1;
      put[i].r=r[i-1]+1;
      put[i].y=y[i-1];
	}
	sort(niz+1,niz+1+N,poy);
	sort(put+1,put+1+M,cmpsw);
	ll pok=N;
	niz[0].y=0;
	for(ll i=M;i>=1;i--){
      while(niz[pok].y>=put[i].y){
         S.insert(niz[pok].id);
         pok--;
      }
      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);
         presek[*it].push_back(i);
      }

  /*    cout<<"PUT "<<put[i].l<<" "<<put[i].r<<" "<<put[i].y<<" SECE"<<endl;
      for(ll x:V)
         cout<<x<<" ";
      cout<<endl;
*/

      for(ll j=1;j<V.size();j++){
         ll pr=V[j-1];
         ll tr=V[j];
         ll d=x[tr-1]-x[pr-1];
        // cout<<d<<" ";
         pr=(pr-1)*mostll+presek[pr].size();
         tr=(tr-1)*mostll+presek[tr].size();
         graf[pr].push_back({tr,d});
         graf[tr].push_back({pr,d});
      }
     // cout<<endl;
	}
	for(ll i=1;i<=N;i++){
      for(ll j=1;j<presek[i].size();j++){
         ll d=put[presek[i][j-1]].y-put[presek[i][j]].y;
         ll a=(i-1)*mostll+j;
         ll b=(i-1)*mostll+j+1;
         graf[a].push_back({b,d});
         graf[b].push_back({a,d});
      }
	}

	/*for(ll i=1;i<=mostll*N;i++){
      cout<<i<<": ";
      for(auto x:graf[i])
         cout<<x.first<<" "<<x.second<<"  ";
      cout<<endl;
	}*/


	Dijkstra(presek[s].size()+(s-1)*mostll,put[presek[s].back()].y);
	ll res=1e18;
	for(ll i=0;i<presek[g].size();i++){
      if(dist[(g-1)*mostll+i+1]==0)
         continue;
      ll d=dist[(g-1)*mostll+i+1];
      d+=put[presek[g][i]].y;
      res=min(res,d);
	}
  	if(res==1e18)
      return -1;
	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:70:11: warning: statement has no effect [-Wunused-value]
   70 |       for(it;it!=S.end();it++){
      |           ^~
walk.cpp:83: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]
   83 |       for(ll j=1;j<V.size();j++){
      |                  ~^~~~~~~~~
walk.cpp:96: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]
   96 |       for(ll j=1;j<presek[i].size();j++){
      |                  ~^~~~~~~~~~~~~~~~~
walk.cpp:115:14: 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]
  115 |  for(ll i=0;i<presek[g].size();i++){
      |             ~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43