Submission #71468

#	Time	Username	Problem	Language	Result	Execution time	Memory
71468		Bruteforceman	Railway Trip (JOI17_railway_trip)	C++11	100 / 100	1242 ms	119892 KiB

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 (stderr)

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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55