Submission #1038965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038965		parsadox2	Sky Walking (IOI19_walk)	C++17	24 / 100	3534 ms	1048576 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int N = 1e5 + 10;
const long long inf = 1e18;

int n , m , a[N] , pos[N];
vector <int> all[N];
vector <long long> dis[N];
vector <bool> marked[N];
vector <vector<pair<pair<int , int> , int>>> adj[N];

struct bridge{
	int l , r , y;
};
vector <bridge> vec;

bool cmp(bridge aa , bridge bb)
{
	return aa.y < bb.y;
}

struct SEG{
	int mx[N << 2];
	void Build(int node = 1 , int nl = 0 , int nr = n)
	{
		if(nr - nl == 1)
		{
			mx[node] = a[nl];
			return;
		}
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Build(lc , nl , mid);  Build(rc , mid , nr);
		mx[node] = max(mx[lc] , mx[rc]);
	}
	int Get(int id , int val , int node = 1 , int nl = 0 , int nr = n)
	{
		if(nr <= id || mx[node] < val)
			return -1;
		if(nr - nl == 1)
			return nl;
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		int tmp = Get(id , val , lc , nl , mid);
		if(tmp == -1)
			return tmp = Get(id , val , rc , mid , nr);
		return tmp;
	}
} seg;

void Add(int l , int r , int y)
{
	int now = l;
	all[now].push_back(y);
	adj[now].emplace_back();
	while(now != r)
	{
		int id = seg.Get(now + 1 , y);
		all[id].push_back(y);
		adj[id].emplace_back();
		adj[now].back().push_back(make_pair(make_pair(id , all[id].size() - 1) , pos[id] - pos[now]));
		adj[id].back().push_back(make_pair(make_pair(now , all[now].size() - 1) , pos[id] - pos[now]));
		now = id;
	}
}

void Dij()
{
	priority_queue <pair<long long , pair<int , int>>> pq;
	for(int i = 0 ; i < n ; i++)  for(int j = 0 ; j < all[i].size() ; j++)
		pq.push(make_pair(-dis[i][j] , make_pair(i , j)));
	while(!pq.empty())
	{
		auto now = pq.top();
		pq.pop();
		long long D = abs(now.F);
		int x = now.S.F , y = now.S.S;
		if(marked[x][y])
			continue;
		//cout << x << " " << y << " ::::  " << D << endl;
		marked[x][y] = true;
		for(auto u : adj[x][y])  if(dis[u.F.F][u.F.S] > D + u.S)
		{
			dis[u.F.F][u.F.S] = D + u.S;
			pq.push(make_pair(-dis[u.F.F][u.F.S] , u.F));
		}
	}
}

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	n = x.size();
	m = l.size();
	for(int i = 0 ; i < n ; i++)
	{
		a[i] = h[i];
		pos[i] = x[i];
	}
	for(int i = 0 ; i < m ; i++)
	{
		vec.push_back({l[i] , r[i] , y[i]});
	}
	sort(vec.begin() , vec.end() , cmp);
	seg.Build();
	for(auto u : vec)
	{
		Add(u.l , u.r , u.y);
	}
	for(int i = 0 ; i < n ; i++)  for(int j = 0 ; j + 1 < all[i].size() ; j++)
	{
		adj[i][j].push_back(make_pair(make_pair(i , j + 1) , all[i][j + 1] - all[i][j]));
		adj[i][j + 1].push_back(make_pair(make_pair(i , j) , all[i][j + 1] - all[i][j]));
	}
	/*for(int i = 0 ; i < n ; i++)  for(int j = 0 ; j < all[i].size() ; j++)
	{
		cout << i << " " << j << " : " << all[i][j] << endl;
		for(auto u : adj[i][j])
			cout << u.F.F << " " << u.F.S << " " << u.S << endl;
	}*/
	for(int i = 0 ; i < n ; i++)
	{
		dis[i].resize(all[i].size() , inf);
		marked[i].resize(all[i].size());
	}
	for(int i = 0 ; i < all[s].size() ; i++)
		dis[s][i] = all[s][i];
	Dij();
	long long res = inf;
	for(int i = 0 ; i < all[g].size() ; i++)
		res = min(res , dis[g][i] + all[g][i]);
	if(res == inf)
		res = -1;
	return res;
}

Compilation message (stderr)

walk.cpp: In function 'void Dij()':
walk.cpp:73:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for(int i = 0 ; i < n ; i++)  for(int j = 0 ; j < all[i].size() ; j++)
      |                                                ~~^~~~~~~~~~~~~~~
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:111:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for(int i = 0 ; i < n ; i++)  for(int j = 0 ; j + 1 < all[i].size() ; j++)
      |                                                ~~~~~~^~~~~~~~~~~~~~~
walk.cpp:127:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |  for(int i = 0 ; i < all[s].size() ; i++)
      |                  ~~^~~~~~~~~~~~~~~
walk.cpp:131:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |  for(int i = 0 ; i < all[g].size() ; i++)
      |                  ~~^~~~~~~~~~~~~~~

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