Submission #459517

#	Time	Username	Problem	Language	Result	Execution time	Memory
459517		flappybird	Sky Walking (IOI19_walk)	C++14	43 / 100	1850 ms	114992 KiB

walk

//이왜진???
#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 (stderr)

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 / 10
• Subtask 2: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 0 / 43