oj.uz

Submission #974731

# Submission time Handle Problem Language Result Execution time Memory
974731 2024-05-03T17:31:32 Z NemanjaSo2005 Sky Walking (IOI19_walk) C++17
0 / 100
 1067 ms 434632 KB 
#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

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++){
      |                  ~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 64052 KB Output is correct
2 Correct 16 ms 63836 KB Output is correct
3 Correct 15 ms 63836 KB Output is correct
4 Runtime error 62 ms 129332 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 63836 KB Output is correct
2 Correct 14 ms 64044 KB Output is correct
3 Correct 689 ms 144876 KB Output is correct
4 Correct 729 ms 153364 KB Output is correct
5 Correct 358 ms 138724 KB Output is correct
6 Correct 337 ms 130616 KB Output is correct
7 Correct 358 ms 140884 KB Output is correct
8 Correct 833 ms 164852 KB Output is correct
9 Correct 472 ms 140628 KB Output is correct
10 Correct 1067 ms 184204 KB Output is correct
11 Correct 345 ms 111440 KB Output is correct
12 Correct 227 ms 95180 KB Output is correct
13 Correct 861 ms 173200 KB Output is correct
14 Runtime error 230 ms 188164 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 80468 KB Output is correct
2 Runtime error 512 ms 434632 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 80468 KB Output is correct
2 Runtime error 512 ms 434632 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 64052 KB Output is correct
2 Correct 16 ms 63836 KB Output is correct
3 Correct 15 ms 63836 KB Output is correct
4 Runtime error 62 ms 129332 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -