답안 #71468

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
71468 2018-08-24T19:00:21 Z Bruteforceman Railway Trip (JOI17_railway_trip) C++11
100 / 100
1242 ms 119892 KB
#include "bits/stdc++.h"
using namespace std;
#define right sadfsdf
#define left sfdfdff
const int maxn = 200010;

int n, k, q;
int a[100010];
int left[100010];
int right[100010];
int l[maxn];
int r[maxn];
const int logn = 18;


typedef pair <int, int> pii;
vector <int> g[maxn];
int dp[2][2][logn + 1][maxn];
int par[logn + 1][maxn];
int dep[maxn];
int pos[maxn];
const int inf = 1e9;

void dfs(int x) {
	for(auto i : g[x]) {
		dep[i] = 1 + dep[x];
		dfs(i);
	} 
}
int lca(int p, int q) {
	if(dep[p] > dep[q]) swap(p, q);
	for(int i = logn; i >= 0; i--) {
		if(dep[q] - (1 << i) >= dep[p]) {
			q = par[i][q];
		}
	}
	if(p == q) return p;
	for(int i = logn; i >= 0; i--) {
		if(par[i][p] != par[i][q]) {
			p = par[i][p];
			q = par[i][q];
		}
	}
	return par[0][p];
}
int lift(int p, int depth) {
	for(int i = logn; i >= 0; i--) {
		if(dep[p] - (1 << i) >= depth) {
			p = par[i][p];
		}
	} 
	return p;
}

int dist(int p, int x, int q, int y) {
	int idp = pos[p];
	int idq = pos[q];
	if(idp > idq) {
		swap(idp, idq);
		swap(x, y);
		swap(p, q);
	}
	int opt = inf;
	opt = min(opt, idq + y - idp - x);
	if(par[0][p]) opt = min(opt, dp[x][0][0][p] + dp[y][1][0][q] + 1);
	if(par[0][p]) opt = min(opt, dp[x][1][0][p] + dp[y][0][0][q] + 1);
	return opt;
}	

int distance(int p, int x, int q, int y) {
	if(p == 0 || q == 0) return inf; 
	if(dep[p] > dep[q]) {
		swap(p, q);
		swap(x, y);
	}
	int anc = lca(p, q);
	int pd[2];
	int qd[2];
	memset(pd, 0, sizeof pd);
	memset(qd, 0, sizeof qd);
	pd[x ^ 1] = 1;
	qd[y ^ 1] = 1; 

	for(int i = logn; i >= 0; i--) {
		if(dep[p] - (1 << i) > dep[anc]) {
			int aa = min(pd[1] + dp[1][0][i][p], pd[0] + dp[0][0][i][p]);
			int bb = min(pd[1] + dp[1][1][i][p], pd[0] + dp[0][1][i][p]);
			p = par[i][p];
			pd[0] = aa;
			pd[1] = bb;
		}
	}
	for(int i = logn; i >= 0; i--) {
		if(dep[q] - (1 << i) > dep[anc]) {
			int aa = min(qd[1] + dp[1][0][i][q], qd[0] + dp[0][0][i][q]);
			int bb = min(qd[1] + dp[1][1][i][q], qd[0] + dp[0][1][i][q]);
			q = par[i][q];
			qd[0] = aa;
			qd[1] = bb;
		}
	}
	int ans = inf;
	if(p != anc) {
		for(int i = 0; i <= 1; i++) {
			for(int j = 0; j <= 1; j++) {
				ans = min(ans, pd[i] + qd[j] + dist(p, i, q, j));
			}
		}
	} else {
		for(int i = 0; i <= 1; i++) {
			for(int j = 0; j <= 1; j++) {
				ans = min(ans, pd[i] + qd[j] + dp[j][i][0][q]);
			}
		}	
	}
	// cout << ans-1 << endl;
	return ans-1;
}

map <pii, int> range_id;

int query(int x, int y) {
	if(x == y) return 0;
	int ans = inf;
	int lx = range_id[pii(left[x], x)];
	int rx = range_id[pii(x, right[x])];
	int ly = range_id[pii(left[y], y)];
	int ry = range_id[pii(y, right[y])];
	ans = min(ans, distance(lx, 1, ly, 1));
	if(ans < inf) return ans;
	ans = min(ans, distance(lx, 1, ry, 0));
	if(ans < inf) return ans;
	ans = min(ans, distance(rx, 0, ly, 1));
	if(ans < inf) return ans;
	ans = min(ans, distance(rx, 0, ry, 0));
	return ans;
}

int main(int argc, char const *argv[])
{
	scanf("%d %d %d", &n, &k, &q);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	int idx = 0;
	stack <int> s;
	set <pii> range;

	for(int i = 1; i <= n; i++) {
		while(!s.empty() && a[s.top()] < a[i]) {
			s.pop();
		}
		if(i > 1) {
			left[i] = s.top();
			range.emplace(left[i], i);
		}
		s.push(i);
	}
	while(!s.empty()) s.pop();
	for(int i = n; i >= 1; i--) {
		while(!s.empty() && a[s.top()] < a[i]) {
			s.pop();
		}
		if(i < n) {
			right[i] = s.top();
			range.emplace(i, right[i]);
		}
		s.push(i); 
	} 
	for(auto i : range) {
		l[++idx] = i.first;
		r[idx] = i.second;
		range_id[i] = idx;
	}
	vector <pii> v;
	for(int i = 1; i <= idx; i++) {
		v.emplace_back(pii(r[i] - l[i], i));
	}
	sort(v.begin(), v.end());
	set <pii> ss;
	for(auto i : v) {
		int p = l[i.second];
		int q = r[i.second];
		while(true) {
			auto it = ss.lower_bound(pii(p, -1));
			if(it == ss.end()) break;
			if(r[it -> second] <= q) {
				par[0][it -> second] = i.second;
				g[i.second].emplace_back(it -> second);
				ss.erase(it);
			} else {
				break;
			}
		}
		ss.insert(pii(p, i.second));
	}
	for(auto i : ss) {
		g[0].emplace_back(i.second);
		par[0][i.second] = 0;
	}
	for(int i = 1; i <= logn; i++) {
		for(int j = 1; j <= idx; j++) {
			par[i][j] = par[i - 1][par[i - 1][j]];
		}
	}
	for(int i = 0; i <= idx; i++) {
		int id = 0;
		for(auto j : g[i]) {
			// cout << i << ' ' << j << endl;
			dp[0][0][0][j] = id;
			dp[0][1][0][j] = g[i].size() - id;
			dp[0][0][0][j] = min(dp[0][0][0][j], 1 + dp[0][1][0][j]);
			dp[0][1][0][j] = min(dp[0][1][0][j], 1 + dp[0][0][0][j]);

			dp[1][0][0][j] = id + 1;
			dp[1][1][0][j] = g[i].size() - id - 1;  
			dp[1][0][0][j] = min(dp[1][0][0][j], 1 + dp[1][1][0][j]);
			dp[1][1][0][j] = min(dp[1][1][0][j], 1 + dp[1][0][0][j]);
			pos[j] = ++id;
		}
	}
	for(int i = 1; i <= logn; i++) {
		for(int j = 0; j <= 1; j++) {
			for(int k = 0; k <= 1; k++) {
				for(int l = 0; l <= idx; l++) {
					int opt = inf;
					for(int x = 0; x <= 1; x++) {
						opt = min(opt, dp[j][x][i - 1][l] + dp[x][k][i - 1][par[i - 1][l]]);
					}
					dp[j][k][i][l] = opt; 
				}
			}
		}
	}
	dfs(0);
	for(int i = 1; i <= q; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		printf("%d\n", query(x, y));
	}
	return 0;
}

Compilation message

railway_trip.cpp: In function 'int main(int, const char**)':
railway_trip.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &k, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:143:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
railway_trip.cpp:238:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5752 KB Output is correct
2 Correct 8 ms 5780 KB Output is correct
3 Correct 9 ms 5948 KB Output is correct
4 Correct 8 ms 5948 KB Output is correct
5 Correct 9 ms 5948 KB Output is correct
6 Correct 10 ms 5948 KB Output is correct
7 Correct 10 ms 5948 KB Output is correct
8 Correct 7 ms 5948 KB Output is correct
9 Correct 8 ms 5948 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 6928 KB Output is correct
2 Correct 451 ms 98176 KB Output is correct
3 Correct 437 ms 104092 KB Output is correct
4 Correct 541 ms 108888 KB Output is correct
5 Correct 540 ms 111144 KB Output is correct
6 Correct 454 ms 113632 KB Output is correct
7 Correct 450 ms 114280 KB Output is correct
8 Correct 185 ms 114280 KB Output is correct
9 Correct 241 ms 114280 KB Output is correct
10 Correct 246 ms 114280 KB Output is correct
11 Correct 316 ms 114280 KB Output is correct
12 Correct 281 ms 114280 KB Output is correct
13 Correct 310 ms 114280 KB Output is correct
14 Correct 326 ms 114280 KB Output is correct
15 Correct 316 ms 114280 KB Output is correct
16 Correct 346 ms 114280 KB Output is correct
17 Correct 529 ms 115756 KB Output is correct
18 Correct 492 ms 115820 KB Output is correct
19 Correct 508 ms 115820 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1024 ms 115820 KB Output is correct
2 Correct 1039 ms 115820 KB Output is correct
3 Correct 880 ms 115820 KB Output is correct
4 Correct 994 ms 115820 KB Output is correct
5 Correct 1022 ms 115820 KB Output is correct
6 Correct 1176 ms 115820 KB Output is correct
7 Correct 1139 ms 115820 KB Output is correct
8 Correct 851 ms 115820 KB Output is correct
9 Correct 666 ms 115820 KB Output is correct
10 Correct 723 ms 115820 KB Output is correct
11 Correct 684 ms 115820 KB Output is correct
12 Correct 650 ms 115820 KB Output is correct
13 Correct 715 ms 115820 KB Output is correct
14 Correct 657 ms 115820 KB Output is correct
15 Correct 749 ms 115820 KB Output is correct
16 Correct 856 ms 115820 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1084 ms 117192 KB Output is correct
2 Correct 982 ms 117232 KB Output is correct
3 Correct 1022 ms 117236 KB Output is correct
4 Correct 1053 ms 117376 KB Output is correct
5 Correct 667 ms 117376 KB Output is correct
6 Correct 1076 ms 117376 KB Output is correct
7 Correct 1016 ms 117376 KB Output is correct
8 Correct 906 ms 117376 KB Output is correct
9 Correct 937 ms 117376 KB Output is correct
10 Correct 999 ms 117376 KB Output is correct
11 Correct 1022 ms 117376 KB Output is correct
12 Correct 1077 ms 117376 KB Output is correct
13 Correct 1095 ms 117376 KB Output is correct
14 Correct 1104 ms 117376 KB Output is correct
15 Correct 1131 ms 117376 KB Output is correct
16 Correct 1242 ms 119892 KB Output is correct
17 Correct 1032 ms 119892 KB Output is correct
18 Correct 1180 ms 119892 KB Output is correct
19 Correct 1094 ms 119892 KB Output is correct
20 Correct 1037 ms 119892 KB Output is correct
21 Correct 1054 ms 119892 KB Output is correct
22 Correct 1051 ms 119892 KB Output is correct
23 Correct 1086 ms 119892 KB Output is correct