제출 #418120

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
418120		8e7	밀림 점프 (APIO21_jumps)	C++14	100 / 100	1358 ms	88128 KiB

jumps

//Challenge: Accepted
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <stack>
#include <set>
#include <map>
#include <assert.h>
#include <queue>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
#define maxn 200005
#define mod 1000000007
using namespace std;
using namespace __gnu_pbds;
void debug() {
	cout << endl;
}
template<class T, class ...U> void debug(T a, U ...b) {
	cout << a << " ";debug(b...);
}
template<class T> void pary(T l, T r) {
	while (l != r) {
		cout << *l << " ";
		l++;
	}
	cout << endl;
}
 
//template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//gp_hash_table<int, int> mp;
//find by order, order of key
 
#include "jumps.h"
 
vector<int> adj[maxn];
int to[18][maxn], anc[18][maxn], par[maxn], dep[maxn];
int tom[18][maxn], ancm[18][maxn];
int lef[maxn], rig[maxn];
int ti = 0;
void dfs(int n, int par, int d) {
	dep[n] = d;
	lef[n] = n, rig[n] = n;
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n, d + 1);
			lef[n] = min(lef[n], lef[v]);
			rig[n] = max(rig[n], rig[v]);
		}
	}
}
void init(int N, vector<int> H) {
	stack<int> stk;
	for (int i = 0;i < N;i++) par[i] = N, lef[i] = N, rig[i] = N;
	for (int i = 0;i < N;i++) {
		vector<int> po;
		while (stk.size() && H[i] >= H[stk.top()]) {
			po.push_back(stk.top());
			rig[stk.top()] = i;
			stk.pop();
		}
		if (po.size()) {
			adj[i].push_back(po.back());
			par[po.back()] = i;
			for (int j = 0;j < po.size() - 1;j++) {
				adj[po[j + 1]].push_back(po[j]);
				par[po[j]] = po[j + 1];
			}
		}
		if (stk.size()) lef[i] = stk.top();
		stk.push(i);
	}	
	int prv = -1;
	while (stk.size()) {
		int cur = stk.top();
		if (prv != -1) {
			adj[cur].push_back(prv);
			par[prv] = cur;
		}
		prv = cur;
		stk.pop();
	}
	//pary(par, par + N);
	for (int i = 0;i < N;i++) {
		anc[0][i] = par[i], ancm[0][i] = tom[0][i] = max(i, par[i]);
		if (par[i] == lef[i]) to[0][i] = rig[i];
		else to[0][i] = lef[i];
	}
	dep[N] = -1, to[0][N] = anc[0][N] = N;
	tom[0][N] = ancm[0][N] = N;
	for (int i = 1;i < 18;i++) {
		for (int j = 0;j <= N;j++) {
			to[i][j] = to[i - 1][to[i - 1][j]], anc[i][j] = anc[i - 1][anc[i - 1][j]];
			tom[i][j] = max(tom[i - 1][j], tom[i - 1][to[i - 1][j]]);
			ancm[i][j] = max(ancm[i - 1][j], ancm[i - 1][anc[i - 1][j]]);
		}
	}
	int root = max_element(H.begin(), H.end()) - H.begin();
	dfs(root, root, 0);
}
int curl = 0, curr = 0;
int dis(int s, int t) {
	int dif = dep[s] - dep[t];
	if (dif < 0) return -1;
	int ret = 0, cur = s;
	for (int i = 17;i >= 0;i--) {
		if (dep[to[i][cur]] >= dep[t] && max(to[i][cur], tom[i][cur]) < curl) {
			cur = to[i][cur];
			ret += 1<<i;
		}	
	}
	if (curl <= to[0][cur] && to[0][cur] <= curr) return ret + 1;
	for (int i = 17;i >= 0;i--) {
		if (dep[anc[i][cur]] >= dep[t] && ancm[i][cur] < curl) {
			cur = anc[i][cur];
			ret += 1<<i;
		}
	}
	if (curl <= anc[0][cur] && anc[0][cur] <= curr) return ret + 1;
	return -1;
}
int lca(int a, int b) {
	if (dep[a] < dep[b]) swap(a, b);
	int hdif = dep[a] - dep[b], cnt = 0;
	while (hdif) {
		if (hdif & 1) {
			a = anc[cnt][a];
		}
		hdif>>=1, cnt++;
	}
	if (a == b) return a;
	for (int i = 17;i >= 0;i--) {
		if (anc[i][a] != anc[i][b]) {
			a = anc[i][a], b = anc[i][b];
		}
	}
	return anc[0][a];
}
int minimum_jumps(int A, int B, int C, int D) {
	int ret = -1;
	int m = lca(C, D);
	int l = max(lef[m], A), r = min(rig[m], B);
	if (r < l) return -1;	
	curl = C, curr = D;
	return dis(lca(l, r), m);
}
/*
7 4
3 2 1 6 4 5 7
4 5 6 6
0 3 6 6
0 1 2 2
1 1 3 3
 
8 5
1 2 3 4 5 6 7 8
0 5 6 7
0 2 6 7
0 4 5 5
3 3 5 7
1 2 6 6
*/

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |    for (int j = 0;j < po.size() - 1;j++) {
      |                   ~~^~~~~~~~~~~~~~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:147:6: warning: unused variable 'ret' [-Wunused-variable]
  147 |  int ret = -1;
      |      ^~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19