oj.uz

Submission #974730

# Submission time Handle Problem Language Result Execution time Memory
974730 2024-05-03T17:30:32 Z NemanjaSo2005 Sky Walking (IOI19_walk) C++17
0 / 100
 980 ms 225228 KB 
#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;
}
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:77:11: warning: statement has no effect [-Wunused-value]
   77 |       for(it;it!=S.end();it++){
      |           ^~
walk.cpp:86: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]
   86 |       for(ll j=1;j<V.size();j++){
      |                  ~^~~~~~~~~
walk.cpp:99: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]
   99 |       for(ll j=1;j<koji[i].size();j++){
      |                  ~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33116 KB Output is correct
2 Correct 9 ms 33116 KB Output is correct
3 Correct 8 ms 33116 KB Output is correct
4 Runtime error 32 ms 67116 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 7 ms 33116 KB Output is correct
2 Correct 7 ms 33116 KB Output is correct
3 Correct 693 ms 113960 KB Output is correct
4 Correct 689 ms 122964 KB Output is correct
5 Correct 353 ms 107348 KB Output is correct
6 Correct 366 ms 99152 KB Output is correct
7 Correct 352 ms 109520 KB Output is correct
8 Correct 828 ms 134716 KB Output is correct
9 Correct 476 ms 111888 KB Output is correct
10 Correct 980 ms 153944 KB Output is correct
11 Correct 348 ms 82124 KB Output is correct
12 Correct 209 ms 65004 KB Output is correct
13 Correct 901 ms 143156 KB Output is correct
14 Runtime error 202 ms 121684 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 85 ms 50000 KB Output is correct
2 Runtime error 246 ms 225228 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 85 ms 50000 KB Output is correct
2 Runtime error 246 ms 225228 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 17 ms 33116 KB Output is correct
2 Correct 9 ms 33116 KB Output is correct
3 Correct 8 ms 33116 KB Output is correct
4 Runtime error 32 ms 67116 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -