Submission #892921

#	Time	Username	Problem	Language	Result	Execution time	Memory
892921		KaleemRazaSyed	Sky Walking (IOI19_walk)	C++17	24 / 100	3568 ms	1007576 KiB

walk

#include<bits/stdc++.h>

using namespace std;

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

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

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];
}

#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;
      for(auto it = st.lower_bound(f); it!= st.end() && *it <= s; it++){
	int b = *it;
	if(h[b] < d){
	  rem.push_back(b);
	  continue;
	}
	nv.push_back(b);
	if(high[b] == d) continue;
	
	int yi = high[b];
	int xi = x[b];
	int v = mp[{xi, yi}];
	mp[{xi, d}] = n;
	high[b] = d;
	G[n].push_back({v, d - yi});
	G[v].push_back({n, d - yi});
	n++;
      }

      for(int b = 0; b < (int)nv.size() - 1; b++) {
	int v1 = mp[{x[nv[b]], d}], v2 = mp[{x[nv[b + 1]], d}];
	G[v1].push_back({v2, x[nv[b+1]] - x[nv[b]]});
	G[v2].push_back({v1, x[nv[b+1]] - x[nv[b]]});
      }

      for(int b : rem)
	st.erase(b);
	
    }
  
  ll d = dij(s, g, n);
  if(d == inf) return -1;
  return d;
}
/*
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++)
      |                  ~~^~~~~~~~~~~~~~~~~

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