Submission #71468

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
71468	2018-08-24T19:00:21 Z	Bruteforceman	Railway Trip (JOI17_railway_trip)	C++11	100 / 100	1242 ms	119892 KB

railway_trip

#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);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	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

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	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

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	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

Subtask #4

55.0 / 55.0

#	Verdict	Execution time	Memory	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