oj.uz

Submission #459517

# Submission time Handle Problem Language Result Execution time Memory
459517 2021-08-08T15:00:46 Z flappybird Sky Walking (IOI19_walk) C++14
43 / 100
 1850 ms 114992 KB 
//이왜진???
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll N, M;
vector<vector<ll>> branch, ind, st, en;
vector<vector<pair<ll, ll>>> adj;
vector<pair<ll, ll>> node;
ll getind(ll xx, ll hh) {
	if (xx < 0) return -1;
	if (xx >= N) return -1;
	ll idx;
	idx = lower_bound(branch[xx].begin(), branch[xx].end(), hh) - branch[xx].begin();
	if (idx >= branch[xx].size()) return -1;
	if (branch[xx][idx] == hh) return ind[xx][idx];
}
bool chk(pair<ll, ll> p, ll x, ll y) {
	//return p.first <= x && x <= p.second && p.first <= y && y <= p.second;
	return p.second <= x && x <= p.first && p.second <= y && y <= p.first;
}
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();
	tie(S, G) = make_tuple(min(S, G), max(S, G));
	ll i;
	//split
	for (i = 0; i < M; i++) {
		if ((l[i] < S && S < r[i] && (y[i] <= h[S])) && (l[i] < G && G < r[i] && (y[i] <= h[G]))) {
			l.push_back(S);
			l.push_back(G);
			r.push_back(G);
			r.push_back(r[i]);
			y.push_back(y[i]);
			y.push_back(y[i]);
			r[i] = S;
		}
		else if (l[i] < S && S < r[i] && (y[i] <= h[S])) {
			l.push_back(S);
			r.push_back(r[i]);
			y.push_back(y[i]);
			r[i] = S;
		}
		else if (l[i] < G && G < r[i] && (y[i] <= h[G])) {
			l.push_back(G);
			r.push_back(r[i]);
			y.push_back(y[i]);
			r[i] = G;
		}
	}
	M = l.size();
	branch.resize(N);
	for (i = 0; i < M; i++) {
		branch[l[i]].push_back(y[i]);
		branch[r[i]].push_back(y[i]);
	}
	multiset<ll> ms;
	st.resize(N);
	en.resize(N);
	for (i = 0; i < M; i++) st[l[i]].push_back(i), en[r[i]].push_back(i);
	ll cnt = N - 1, j;
	for (i = 0; i < N; i++) {
		for (auto x : st[i]) ms.insert(y[x]);
		ll sz = branch[i].size();
		for (j = 0; j < sz; j++) {
			auto lb = ms.lower_bound(branch[i][j]);
			if (lb != ms.end() && *lb <= h[i]) branch[i].push_back(*lb);
			if (ms.lower_bound(branch[i][j]) != ms.begin()) branch[i].push_back(*(--ms.lower_bound(branch[i][j])));
		}
		for (auto x : en[i]) ms.erase(ms.find(y[x]));
	}
	ind.resize(N);
	for (i = 0; i < N; i++) {
		sort(branch[i].begin(), branch[i].end());
		branch[i].erase(unique(branch[i].begin(), branch[i].end()), branch[i].end());
		ind[i].resize(branch[i].size());
		for (j = 0; j < branch[i].size(); j++) ind[i][j] = ++cnt;
	}
	ll V = cnt + 1;
	adj.resize(V);
	node.resize(V);
	for (i = 0; i < N; i++) {
		for (j = 0; j < branch[i].size(); j++) {
			node[ind[i][j]] = {i, branch[i][j]};
		}
	}
	map<ll, vector<ll>> mp;
	map<ll, vector<pair<ll, ll>>> mr;
	for (i = 0; i < M; i++) mr[y[i]].push_back({ x[r[i]], x[l[i]] });
	for (i = N; i < V; i++) mp[node[i].second].push_back(node[i].first);
	for (auto it = mp.begin(); it != mp.end(); it++) sort(it->second.begin(), it->second.end());
	for (auto it = mr.begin(); it != mr.end(); it++) sort(it->second.begin(), it->second.end());
	for (i = N; i < V; i++) {
		ll cid;
		ll nh = node[i].second;
		cid = lower_bound(mp[nh].begin(), mp[nh].end(), node[i].first) - mp[nh].begin();
		ll pv, ne;
		pv = ne = -1;
		if (cid - 1 >= 0) pv = getind(mp[nh][cid - 1], nh);
		if (cid + 1 < mp[nh].size()) ne = getind(mp[nh][cid + 1], nh);
		vector<pair<ll, ll>>::iterator it;
		//if (~pv && (node[pv].first < node[i].first) && ((it = upper_bound(mr[nh].begin(), mr[nh].end(), pair<ll, ll>((ll)x[node[i].first], 0))) != mr[nh].begin()) && chk(*(--it), (ll)x[node[i].first], (ll)x[node[pv].first])) adj[i].push_back({ pv, (ll)(x[node[i].first] - x[node[pv].first]) }), adj[pv].push_back({ i, (ll)(x[node[i].first] - x[node[pv].first]) });
		if (~ne && (node[i].first < node[ne].first) && ((it = lower_bound(mr[nh].begin(), mr[nh].end(), pair<ll, ll>((ll)x[node[ne].first], 0))) != mr[nh].end()) && chk(*it, (ll)x[node[i].first], (ll)x[node[ne].first])) adj[i].push_back({ ne, (ll)(x[node[ne].first] - x[node[i].first]) }), adj[ne].push_back({ i, (ll)(x[node[ne].first] - x[node[i].first]) });
	}
	for (i = 0; i < N; i++) {
		if (branch[i].empty()) continue;
		adj[ind[i][0]].push_back({ i, branch[i][0] });
		adj[i].push_back({ ind[i][0], branch[i][0] });
		for (j = 1; j < branch[i].size(); j++) {
			adj[ind[i][j - 1]].push_back({ ind[i][j], branch[i][j] - branch[i][j - 1] });
			adj[ind[i][j]].push_back({ ind[i][j - 1], branch[i][j] - branch[i][j - 1] });
		}
	}
	priority_queue<pair<ll, ll>> pq;
	vector<ll> dist(V, 1e16);
	dist[S] = 0;
	pq.push({ 0, S });
	while (!pq.empty()) {
		pair<ll, ll> t = pq.top();
		pq.pop();
		ll v = t.second;
		if (dist[v] != -t.first) continue;
		for (auto x : adj[v]) {
			if (dist[x.first] > -t.first + x.second) {
				dist[x.first] = -t.first + x.second;
				pq.emplace(-dist[x.first], x.first);
			}
		}
	}
	if(dist[G]>=1e16) return -1;
	return dist[G];
}

Compilation message

walk.cpp: In function 'll getind(ll, ll)':
walk.cpp:16:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  if (idx >= branch[xx].size()) return -1;
      |      ~~~~^~~~~~~~~~~~~~~~~~~~
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:78:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for (j = 0; j < branch[i].size(); j++) ind[i][j] = ++cnt;
      |               ~~^~~~~~~~~~~~~~~~~~
walk.cpp:84:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (j = 0; j < branch[i].size(); j++) {
      |               ~~^~~~~~~~~~~~~~~~~~
walk.cpp:101:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   if (cid + 1 < mp[nh].size()) ne = getind(mp[nh][cid + 1], nh);
      |       ~~~~~~~~^~~~~~~~~~~~~~~
walk.cpp:98:6: warning: variable 'pv' set but not used [-Wunused-but-set-variable]
   98 |   ll pv, ne;
      |      ^~
walk.cpp:110:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for (j = 1; j < branch[i].size(); j++) {
      |               ~~^~~~~~~~~~~~~~~~~~
walk.cpp: In function 'll getind(ll, ll)':
walk.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
   18 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 292 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 292 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 288 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1016 ms 82584 KB Output is correct
4 Correct 959 ms 104236 KB Output is correct
5 Correct 682 ms 80960 KB Output is correct
6 Correct 689 ms 79160 KB Output is correct
7 Correct 640 ms 81468 KB Output is correct
8 Correct 1099 ms 85528 KB Output is correct
9 Correct 1016 ms 95296 KB Output is correct
10 Incorrect 1049 ms 102804 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 17204 KB Output is correct
2 Correct 1336 ms 91884 KB Output is correct
3 Correct 1482 ms 94140 KB Output is correct
4 Correct 1679 ms 113392 KB Output is correct
5 Correct 1801 ms 114532 KB Output is correct
6 Correct 1756 ms 110600 KB Output is correct
7 Correct 628 ms 67144 KB Output is correct
8 Correct 824 ms 84536 KB Output is correct
9 Correct 1583 ms 108584 KB Output is correct
10 Correct 478 ms 70420 KB Output is correct
11 Correct 19 ms 8396 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 17204 KB Output is correct
2 Correct 1336 ms 91884 KB Output is correct
3 Correct 1482 ms 94140 KB Output is correct
4 Correct 1679 ms 113392 KB Output is correct
5 Correct 1801 ms 114532 KB Output is correct
6 Correct 1756 ms 110600 KB Output is correct
7 Correct 628 ms 67144 KB Output is correct
8 Correct 824 ms 84536 KB Output is correct
9 Correct 1583 ms 108584 KB Output is correct
10 Correct 478 ms 70420 KB Output is correct
11 Correct 19 ms 8396 KB Output is correct
12 Correct 1503 ms 94104 KB Output is correct
13 Correct 1448 ms 112480 KB Output is correct
14 Correct 1733 ms 114560 KB Output is correct
15 Correct 822 ms 89140 KB Output is correct
16 Correct 816 ms 90356 KB Output is correct
17 Correct 954 ms 100756 KB Output is correct
18 Correct 869 ms 89164 KB Output is correct
19 Correct 856 ms 90440 KB Output is correct
20 Correct 710 ms 65624 KB Output is correct
21 Correct 50 ms 17092 KB Output is correct
22 Correct 885 ms 91884 KB Output is correct
23 Correct 786 ms 90448 KB Output is correct
24 Correct 740 ms 79172 KB Output is correct
25 Correct 785 ms 87968 KB Output is correct
26 Correct 620 ms 76068 KB Output is correct
27 Correct 1753 ms 114992 KB Output is correct
28 Correct 1415 ms 111428 KB Output is correct
29 Correct 1850 ms 110124 KB Output is correct
30 Correct 695 ms 66940 KB Output is correct
31 Correct 1690 ms 108668 KB Output is correct
32 Correct 432 ms 63512 KB Output is correct
33 Correct 392 ms 67684 KB Output is correct
34 Correct 554 ms 77172 KB Output is correct
35 Correct 630 ms 74540 KB Output is correct
36 Correct 408 ms 66924 KB Output is correct
37 Correct 255 ms 56920 KB Output is correct
38 Correct 293 ms 64972 KB Output is correct
39 Correct 702 ms 87092 KB Output is correct
40 Correct 399 ms 64688 KB Output is correct
41 Correct 280 ms 60488 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 292 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 292 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 288 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1016 ms 82584 KB Output is correct
21 Correct 959 ms 104236 KB Output is correct
22 Correct 682 ms 80960 KB Output is correct
23 Correct 689 ms 79160 KB Output is correct
24 Correct 640 ms 81468 KB Output is correct
25 Correct 1099 ms 85528 KB Output is correct
26 Correct 1016 ms 95296 KB Output is correct
27 Incorrect 1049 ms 102804 KB Output isn't correct
28 Halted 0 ms 0 KB -