oj.uz

Submission #831793

# Submission time Handle Problem Language Result Execution time Memory
831793 2023-08-20T15:03:01 Z Red_Inside Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 11856 KB 
#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;

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

int t[4*maxn];
void build(int v, int tl, int tr)
{
	if(tl == tr)
	{
		t[v] = h[tl];
		return;
	}
	build(v * 2, tl, (tl + tr) / 2);
	build(v * 2 + 1, (tl + tr) / 2 + 1, tr);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}

int getup(int v, int tl, int tr, int l, int val)
{
	if(t[v] < val || tr < l) return n+1;
	if(tl == tr) return tl;
	int ret1 = getup(v * 2, tl, (tl + tr) / 2, l, val);
	int ret2 = getup(v * 2 + 1, (tl + tr) / 2 + 1, tr, l, val);
	if(ret1 != n+1) return ret1;
	return ret2;
}

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];
	}
	build(1, 1, n);
	forn(1, i, m)
	{
		int cur = getup(1, 1, n, l[i], y[i]);
		while(cur <= r[i])
		{
			dot[cur].pb(y[i]);
			cur = getup(1, 1, n, cur+1, 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 <int, 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;
		int cur = getup(1, 1, n, l[i], y[i]);
		while(cur <= r[i])
		{
			int se = lower_bound(all(dot[cur]), y[i]) - dot[cur].begin();
			se = ver[cur][se];
			if(last != -1)
			{
				edge[se].pb({last, x[cur]-x[indx]});
				edge[last].pb({se, x[cur]-x[indx]});
			}
			last = se;
			indx = cur;
			cur = getup(1, 1, n, cur+1, y[i]);
		}
	}
/*	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

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<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(j, i, n) for(int i = j; i < n; ++i)
......
   82 |   FOR(0, j, dot[i].size()) ver[i][j] = ++cnt;
      |          ~~~~~~~~~~~~~~~~              
walk.cpp:82:3: note: in expansion of macro 'FOR'
   82 |   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<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(j, i, n) for(int i = j; i < n; ++i)
......
   88 |   FOR(1, j, dot[i].size())
      |          ~~~~~~~~~~~~~~~~              
walk.cpp:88:3: note: in expansion of macro 'FOR'
   88 |   FOR(1, j, dot[i].size())
      |   ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5012 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5008 KB Output is correct
8 Correct 3 ms 5028 KB Output is correct
9 Correct 2 ms 5012 KB Output is correct
10 Correct 3 ms 5140 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 5008 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 5076 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5016 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Execution timed out 4043 ms 11856 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4048 ms 8724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4048 ms 8724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5012 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5008 KB Output is correct
8 Correct 3 ms 5028 KB Output is correct
9 Correct 2 ms 5012 KB Output is correct
10 Correct 3 ms 5140 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 5008 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 2 ms 5016 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Execution timed out 4043 ms 11856 KB Time limit exceeded
21 Halted 0 ms 0 KB -