Submission #892920

#	Time	Username	Problem	Language	Result	Execution time	Memory
892920		KaleemRazaSyed	Sky Walking (IOI19_walk)	C++17	10 / 100	2062 ms	507864 KiB

walk

#include<bits/stdc++.h>

using namespace std;

#define ll long long
const int N = 1e6+6;
const ll inf = 1e18;
ll dis[N];
int par[N];
vector<pair<int, ll> > G[N];

map<pair<int,int>, int> mp;

inline ll dij(int s, int e, int n)
{
  for(int i = 0; i < n; i++)
    dis[i] = inf, par[i] = -1;
  dis[s] = 0;

  set<pair<ll, int> > st;
  for(int i = 0; i < n; i ++)
    st.insert({dis[i], i});

  while(st.size())
    {
      int u = st.begin()->second;
      st.erase(st.begin());

      for(auto e : G[u]) {
	int v = e.first, w = e.second;
	if(dis[u] + w < dis[v]) {
	  st.erase({dis[v], v});
	  dis[v] = dis[u] + w;
	  par[v] = u;
	  st.insert({dis[v], v});
	}
      }
    }
  return (dis[e] == inf ? -1 : dis[e]);
}

#define F first
#define S second


ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g)
{

  vector<pair<int, pair<int,int> > > skywalks;
  for(int i = 0; i < l.size(); i++)
    skywalks.push_back({y[i], {l[i], r[i]}});

  sort(skywalks.begin(), skywalks.end());
  int n = x.size();
  vector<int> high(x.size(), 0);
  for(int i = 0; i < n; i ++)
    mp[{x[i], 0}] = i;
  set<int> st;
  for(int i = 0; i < n; i ++)
    st.insert(i);
  
  for(int i = 0; i < skywalks.size(); i++)
    {
      int f = skywalks[i].S.F, s = skywalks[i].S.S, d = skywalks[i].F;
      vector<int> nv, rem, xd;
      auto it = st.lower_bound(f);
      for(; it!= st.end() && *it <= s; it++){
	int b = *it;
	if(h[b] < d){
	  rem.push_back(b);
	  continue;
	}
	nv.push_back(mp[{x[b], d}]);
	xd.push_back(x[b]);
	if(high[b] == d) continue;
	int yi = high[b];
	int xi = x[b];
	int v = mp[{xi, yi}];
	mp[{xi, d}] = n;
	nv.pop_back();
	nv.push_back(n);
	high[b] = d;
	G[n].push_back({v, d - yi});
	G[v].push_back({n, d - yi});
	n++;
      }
      int v1 = nv[0];
      for(int b = 1; b < nv.size(); b++) {
	int v2 = nv[b];
	G[v1].push_back({v2, xd[b] - xd[b-1]});
	G[v2].push_back({v1, xd[b] - xd[b-1]});
	v1 = v2;
      }

      for(int r : rem)
	st.erase(r);
	
    }
  
  return dij(s, g, n);
}
/*
int main() {
  int n, m;
  assert(2 == scanf("%d%d", &n, &m));
  vector<int> x(n), h(n);
  for (int i = 0; i < n; i++)
    assert(2 == scanf("%d%d", &x[i], &h[i]));
  vector<int> l(m), r(m), y(m);
  for (int i = 0; i < m; i++)
    assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
  int s, g;
  assert(2 == scanf("%d%d", &s, &g));
  fclose(stdin);

  long long result = min_distance(x, h, l, r, y, s, g);

  printf("%lld\n", result);
  fclose(stdout);
  return 0;
  }
// */

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:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int i = 0; i < l.size(); i++)
      |                  ~~^~~~~~~~~~
walk.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int i = 0; i < skywalks.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~
walk.cpp:88:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |       for(int b = 1; b < nv.size(); b++) {
      |                      ~~^~~~~~~~~~~

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