oj.uz

답안 #563514

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
563514 2022-05-17T11:34:58 Z amunduzbaev Railway Trip (JOI17_railway_trip) C++17
100 / 100
 428 ms 122212 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array

const int N = 2e5 + 5;
const int inf = N;
vector<int> edges[N], pos[N];
int a[N], par[N][20], path[N][20][2][2], p[N];
int st[N][20], tin[N], tout[N], t;
int L[N], R[N], ver[N], sz[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, k, q; cin>>n>>k>>q;
	for(int i=0;i<n;i++){
		cin>>a[i];
		st[i][0] = a[i];
		pos[a[i]].push_back(i);
	}
	
	for(int j=1;j<20;j++){
		for(int i=0;i+(1 << (j - 1)) < n;i++){
			st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j-1]);
		}
	}
	
	auto ger = [&](int l, int r){
		int lg = __lg(r - l + 1);
		return max(st[l][lg], st[r - (1 << lg) + 1][lg]);
	};
	
	int last = 1;
	function<void(int, int, int)> get = [&](int l, int r, int u){
		//~ cout<<l<<" "<<r<<" "<<u<<"\n";
		tin[u] = ++t;
		for(int j=1;j<20;j++){
			par[u][j] = par[par[u][j-1]][j-1];
			//~ if(par[u][j-1]){
				//~ cout<<par[u][j-1]<<" "<<par[par[u][j-1]][j-1]<<"\n";
			//~ }
			for(int t=0;t<2;t++){
				for(int k=0;k<2;k++){
					if(u) path[u][j][t][k] = inf;
					for(int l=0;l<2;l++){
						path[u][j][t][k] = min(path[u][j][t][k], path[u][j-1][t][l] + path[par[u][j-1]][j-1][l][k]);
					}
				}
			}
		}
		if(l + 1 >= r){
			tout[u] = t;
			return;
		}
		
		int mx = ger(l + 1, r - 1);
		int i = upper_bound(pos[mx].begin(), pos[mx].end(), l) - pos[mx].begin();
		int lx = l, P = 0;
		for(;i<(int)pos[mx].size() && pos[mx][i] < r;i++){
			int j = pos[mx][i];
			ver[j] = last;
			edges[u].push_back(last);
			p[last] = P++;
			L[last] = lx, R[last] = j;
			last++, lx = j;
		}
		
		edges[u].push_back(last);
		p[last] = P++;
		sz[u] = P, L[last] = lx, R[last] = r;
		if(!u) sz[u] = N * 2;
		last++;
		for(auto x : edges[u]){
			par[x][0] = u;
			path[x][0][0][0] = min(p[x], sz[u] - p[x] + 1);
			path[x][0][1][1] = min(p[x] + 2, sz[u] - p[x] - 1);
			path[x][0][0][1] = path[x][0][1][0] = min(p[x] + 1, sz[u] - p[x]);
			get(L[x], R[x], x);
		}
		tout[u] = t;
	};
	get(-1, n, 0);
	//~ for(int i=1;i<last;i++){
		//~ for(int j=0;j<3;j++){
			//~ cout<<par[i][j]<<" ";
		//~ } cout<<"\n";
	//~ }
	
	auto is = [&](int a, int b){
		return (tin[a] <= tin[b] && tin[b] <= tout[a]);
	};
	
	auto gg = [&](ar<int, 2>& d, int a, int b){
		for(int j=19;~j;j--){
			if(!is(par[b][j], a)){
				ar<int, 2> T {};
				//~ cout<<d[0]<<" "<<d[1]<<" "<<par[b][j]<<"\n";
				T[0] = min(d[0] + path[b][j][0][0], d[1] + path[b][j][1][0]);
				T[1] = min(d[0] + path[b][j][0][1], d[1] + path[b][j][1][1]);
				swap(T, d);
				b = par[b][j];
			}
		}
		
		return b;
	};
	
	//~ cout<<ver[0]<<"\n";
	
	auto check = [&](int a, int ta, int b, int tb){
		int res = inf;
		if(a == b) return 1;
		//~ cout<<a<<" "<<b<<"\n";
		if(is(b, a)) swap(a, b), swap(tb, ta);
		if(is(a, b)){
			ar<int, 2> d {}; d[!tb]++;
			int v = gg(d, a, b);
			//~ cout<<d[0]<<" "<<d[1]<<" <-\n";
			ar<int, 2> T {};
			T[0] = min(d[0] + path[v][0][0][0], d[1] + path[v][0][1][0]);
			T[1] = min(d[0] + path[v][0][0][1], d[1] + path[v][0][1][1]);
			return T[ta];
		}
		//~ cout<<a<<" "<<b<<"\n";
		ar<int, 2> d1 {}, d2 {};
		d1[!ta]++; d2[!tb]++;
		int v1 = gg(d1, b, a);
		int v2 = gg(d2, a, b);
		
		//~ cout<<d1[0]<<" "<<d1[1]<<"\n";
		//~ cout<<d2[0]<<" "<<d2[1]<<"\n";
		//~ cout<<v1<<" "<<v2<<" "<<p[v1]<<" "<<p[v2]<<"\n";
		
		for(int t=0;t<2;t++){
			for(int k=0;k<2;k++){
				int bet = abs(p[v1] + t - p[v2] - k);
				bet = min({bet, path[v1][0][t][0] + path[v2][0][k][0], path[v1][0][t][1] + path[v2][0][k][1]});
				//~ cout<<t<<" "<<k<<" "<<d1[t]<<" "<<d2[k]<<" "<<bet<<"\n";
				res = min(res, d1[t] + d2[k] + bet);
			}
		}
		//~ cout<<res<<"\n";
		//~ cout<<"\n";
		
		return res;
	};
	
	while(q--){
		int i, j; cin>>i>>j;
		i--, j--;
		int res = inf;
		for(int t=0;t<2;t++){
			for(int k=0;k<2;k++){
				//~ int x = check(ver[i] + t, !t, ver[j] + k, !k);
				//~ cout<<x<<"\n";
				//~ res = min(res, x);
				res = min(res, check(ver[i] + t, !t, ver[j] + k, !k));
				//~ cout<<check(ver[i] + t, !t, ver[j] + k, !k)<<"\n";
			}
		}
		
		cout<<res - 1<<"\n";
		//~ cout<<"\n";
	}
}

/*

10 10 1
10 1 10 2 10 3 9 4 10 10 
1 10

*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 5 ms 9812 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 5 ms 9812 KB Output is correct
8 Correct 5 ms 9812 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10708 KB Output is correct
2 Correct 93 ms 91824 KB Output is correct
3 Correct 100 ms 97312 KB Output is correct
4 Correct 107 ms 101176 KB Output is correct
5 Correct 105 ms 102872 KB Output is correct
6 Correct 108 ms 104992 KB Output is correct
7 Correct 128 ms 106876 KB Output is correct
8 Correct 54 ms 60512 KB Output is correct
9 Correct 103 ms 82048 KB Output is correct
10 Correct 85 ms 73576 KB Output is correct
11 Correct 109 ms 82412 KB Output is correct
12 Correct 103 ms 82320 KB Output is correct
13 Correct 103 ms 81920 KB Output is correct
14 Correct 107 ms 82516 KB Output is correct
15 Correct 115 ms 82312 KB Output is correct
16 Correct 104 ms 82200 KB Output is correct
17 Correct 111 ms 105464 KB Output is correct
18 Correct 116 ms 105520 KB Output is correct
19 Correct 113 ms 108024 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 208 ms 95044 KB Output is correct
2 Correct 217 ms 93896 KB Output is correct
3 Correct 217 ms 96976 KB Output is correct
4 Correct 219 ms 97356 KB Output is correct
5 Correct 213 ms 97772 KB Output is correct
6 Correct 212 ms 98552 KB Output is correct
7 Correct 221 ms 98760 KB Output is correct
8 Correct 176 ms 73240 KB Output is correct
9 Correct 140 ms 62260 KB Output is correct
10 Correct 141 ms 62280 KB Output is correct
11 Correct 152 ms 62304 KB Output is correct
12 Correct 145 ms 62296 KB Output is correct
13 Correct 156 ms 62284 KB Output is correct
14 Correct 150 ms 62408 KB Output is correct
15 Correct 152 ms 63476 KB Output is correct
16 Correct 181 ms 71180 KB Output is correct

Subtask #4
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 248 ms 106816 KB Output is correct
2 Correct 252 ms 106772 KB Output is correct
3 Correct 227 ms 105392 KB Output is correct
4 Correct 259 ms 107432 KB Output is correct
5 Correct 144 ms 62336 KB Output is correct
6 Correct 270 ms 83712 KB Output is correct
7 Correct 277 ms 83736 KB Output is correct
8 Correct 226 ms 75316 KB Output is correct
9 Correct 267 ms 84132 KB Output is correct
10 Correct 276 ms 83936 KB Output is correct
11 Correct 270 ms 83584 KB Output is correct
12 Correct 273 ms 84044 KB Output is correct
13 Correct 262 ms 83916 KB Output is correct
14 Correct 352 ms 102616 KB Output is correct
15 Correct 349 ms 110084 KB Output is correct
16 Correct 428 ms 122212 KB Output is correct
17 Correct 300 ms 94428 KB Output is correct
18 Correct 349 ms 95260 KB Output is correct
19 Correct 354 ms 95340 KB Output is correct
20 Correct 306 ms 90856 KB Output is correct
21 Correct 251 ms 106956 KB Output is correct
22 Correct 240 ms 106940 KB Output is correct
23 Correct 281 ms 109540 KB Output is correct