Submission #71465

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
71465	2018-08-24T18:30:23 Z	Bruteforceman	Railway Trip (JOI17_railway_trip)	C++11	100 / 100	1537 ms	180660 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;
		}
	}
	// cout << p << " " << "pd " << pd[0] << " " << pd[1] << endl;
	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;
			// cout << q << " " << "qd " << qd[0] << " " << qd[1] << endl;
		}
	}
	// cout << q << " " << "qd " << qd[0] << " " << qd[1] << endl;
	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));
				// cout << i << ' ' << j << ' ' << dist(p, i, q, j) << endl; 
			}
		}
	} 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])];
	// cout << lx << ' ' << rx << ' ' << ly << ' ' << ry << endl;
	ans = min(ans, distance(lx, 1, ly, 1));
	ans = min(ans, distance(lx, 1, ry, 0));
	ans = min(ans, distance(rx, 0, ly, 1));
	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:143: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:145: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:240: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	6 ms	5624 KB	Output is correct
2	Correct	7 ms	5860 KB	Output is correct
3	Correct	6 ms	5860 KB	Output is correct
4	Correct	7 ms	5860 KB	Output is correct
5	Correct	7 ms	5860 KB	Output is correct
6	Correct	7 ms	5860 KB	Output is correct
7	Correct	7 ms	5860 KB	Output is correct
8	Correct	10 ms	5912 KB	Output is correct
9	Correct	8 ms	5912 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	6848 KB	Output is correct
2	Correct	348 ms	97804 KB	Output is correct
3	Correct	398 ms	103872 KB	Output is correct
4	Correct	450 ms	108624 KB	Output is correct
5	Correct	438 ms	110692 KB	Output is correct
6	Correct	442 ms	113424 KB	Output is correct
7	Correct	426 ms	114016 KB	Output is correct
8	Correct	204 ms	114016 KB	Output is correct
9	Correct	299 ms	114016 KB	Output is correct
10	Correct	258 ms	114016 KB	Output is correct
11	Correct	324 ms	114016 KB	Output is correct
12	Correct	317 ms	114016 KB	Output is correct
13	Correct	321 ms	114016 KB	Output is correct
14	Correct	315 ms	114016 KB	Output is correct
15	Correct	323 ms	114016 KB	Output is correct
16	Correct	317 ms	114016 KB	Output is correct
17	Correct	432 ms	119252 KB	Output is correct
18	Correct	429 ms	119872 KB	Output is correct
19	Correct	465 ms	120620 KB	Output is correct

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1125 ms	120620 KB	Output is correct
2	Correct	1166 ms	120620 KB	Output is correct
3	Correct	1186 ms	120620 KB	Output is correct
4	Correct	1248 ms	120620 KB	Output is correct
5	Correct	1264 ms	120620 KB	Output is correct
6	Correct	1293 ms	120620 KB	Output is correct
7	Correct	1178 ms	121628 KB	Output is correct
8	Correct	838 ms	121628 KB	Output is correct
9	Correct	652 ms	121628 KB	Output is correct
10	Correct	873 ms	121628 KB	Output is correct
11	Correct	929 ms	121628 KB	Output is correct
12	Correct	662 ms	121628 KB	Output is correct
13	Correct	775 ms	121628 KB	Output is correct
14	Correct	702 ms	121628 KB	Output is correct
15	Correct	648 ms	121628 KB	Output is correct
16	Correct	945 ms	121628 KB	Output is correct

Subtask #4

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1166 ms	143616 KB	Output is correct
2	Correct	1052 ms	145164 KB	Output is correct
3	Correct	1028 ms	146820 KB	Output is correct
4	Correct	1147 ms	148448 KB	Output is correct
5	Correct	743 ms	148448 KB	Output is correct
6	Correct	1022 ms	148448 KB	Output is correct
7	Correct	1106 ms	148448 KB	Output is correct
8	Correct	836 ms	148448 KB	Output is correct
9	Correct	1305 ms	148448 KB	Output is correct
10	Correct	1351 ms	148448 KB	Output is correct
11	Correct	936 ms	148448 KB	Output is correct
12	Correct	1125 ms	148448 KB	Output is correct
13	Correct	1115 ms	148448 KB	Output is correct
14	Correct	1102 ms	152200 KB	Output is correct
15	Correct	1323 ms	160172 KB	Output is correct
16	Correct	1466 ms	171072 KB	Output is correct
17	Correct	1391 ms	171072 KB	Output is correct
18	Correct	1209 ms	171072 KB	Output is correct
19	Correct	1215 ms	171072 KB	Output is correct
20	Correct	1413 ms	171072 KB	Output is correct
21	Correct	1243 ms	177132 KB	Output is correct
22	Correct	1271 ms	178756 KB	Output is correct
23	Correct	1537 ms	180660 KB	Output is correct