Submission #831639

#	Time	Username	Problem	Language	Result	Execution time	Memory
831639		Red_Inside	Sky Walking (IOI19_walk)	C++17	10 / 100	4093 ms	677056 KiB

walk

#include <bits/stdc++.h>

using namespace std;
#define forn(j, i, n) for(int i = j; i <= n; ++i)
#define FOR(j, i, n) for(int i = j; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define nfor(j, i, n) for(int i = n; i >= j; --i)
#define ll long long
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//const int maxn=2e5+10;
#define o cout <<"BUG\n";
#define pii pair <int, int>

using namespace std;

const int maxn = 1e5+10;

ll n, m, x[maxn], y[maxn], h[maxn], l[maxn], r[maxn];
vector <ll> dot[maxn], ver[maxn];

long long min_distance(vector<int> X, vector<int> H, 
vector<int> L2, vector<int> R2, vector<int> Y2, int s, int g)
{
	m = L2.size();
	s++, g++;
	forn(1, i, m)
	{
		l[i] = L2[i-1]+1;
		r[i] = R2[i-1]+1;
		y[i] = Y2[i-1];
	}
	n = X.size();
	forn(1, i, n)
	{
		x[i] = X[i-1];
		h[i] = H[i-1];
	}
	forn(1, i, m)
	{
		forn(l[i], j, r[i])
		{
			if(h[j] >= y[i])
				dot[j].pb(y[i]);
		}
	}
	int cnt = 0;
	forn(1, i, n)
	{
		dot[i].pb(0);
		sort(all(dot[i]));
		dot[i].erase(unique(all(dot[i])), dot[i].end());
		ver[i].assign(dot[i].size(), 0);
		FOR(0, j, dot[i].size()) ver[i][j] = ++cnt;
	}
	vector <vector <pair <ll, ll> > > edge;
	edge.assign(cnt+10, {});
	forn(1, i, n)
	{
		FOR(1, j, dot[i].size())
		{
			edge[ver[i][j]].pb({ver[i][j-1], dot[i][j]-dot[i][j-1]});
			edge[ver[i][j-1]].pb({ver[i][j], dot[i][j]-dot[i][j-1]});
		}
	}
	forn(1, i, m)
	{
		int last = -1;
		int indx = 0;
		forn(l[i], j, r[i])
		{
			if(h[j] < y[i]) continue;
			int se = lower_bound(all(dot[j]), y[i]) - dot[j].begin();
			int nw = ver[j][se];
			if(last != -1)
			{
				edge[last].pb({nw, x[j]-x[indx]});
				edge[nw].pb({last, x[j]-x[indx]});
			}
			indx = j;
			last = nw;
		}
	}
/*	forn(1, i, n)
	{
		cout << " FOR " << i << endl;
		FOR(0, j, dot[i].size()) cout << dot[i][j] << " " << ver[i][j] << endl;
		cout << endl;
	}*/
//	forn(1, i, cnt)
//		for(auto j : edge[i]) cout << i << " " << j.f << " " << j.s << endl;
	ll inf = 1e18;
	vector <ll> dist(cnt+12);
	forn(1, i, cnt)
	{
		dist[i] = inf;
	}
	int v = ver[s][0];
	dist[v] = 0;
	set <pair <ll, int> > st;
	st.insert({0, v});
	while(st.size())
	{
		int v = st.begin()->s;
		st.erase(st.begin());
		for(auto to : edge[v])
		{
			if(dist[to.f] > dist[v] + to.s)
			{
				st.erase({dist[to.f], to.f});
				dist[to.f] = dist[v]+to.s;
				st.insert({dist[to.f], to.f});
			}
		}
	}
	if(dist[ver[g][0]] == inf) return -1;
	return dist[ver[g][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:6:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(j, i, n) for(int i = j; i < n; ++i)
......
   57 |   FOR(0, j, dot[i].size()) ver[i][j] = ++cnt;
      |          ~~~~~~~~~~~~~~~~              
walk.cpp:57:3: note: in expansion of macro 'FOR'
   57 |   FOR(0, j, dot[i].size()) ver[i][j] = ++cnt;
      |   ^~~
walk.cpp:6:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(j, i, n) for(int i = j; i < n; ++i)
......
   63 |   FOR(1, j, dot[i].size())
      |          ~~~~~~~~~~~~~~~~              
walk.cpp:63:3: note: in expansion of macro 'FOR'
   63 |   FOR(1, j, dot[i].size())
      |   ^~~

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