Submission #301840

#	Time	Username	Problem	Language	Result	Execution time	Memory
301840		Kevin_Zhang_TW	Railway Trip (JOI17_railway_trip)	C++17	20 / 100	2033 ms	9532 KiB

railway_trip

#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(i, e) cerr << #i << ' ' << i << e
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
#else
#define DE(...) 0
void debug(...) {}
#endif
const int maxn = 100010, SQ = 400, inf = maxn;
int n, k, q, v[maxn], res[maxn];
pair<int,int> qr[maxn];
vector<int> edge[maxn];
void init() {
	stack<int> st;
	st.push(1);
	for (int i = 2;i <= n;++i) {
		while (st.size() && v[i] > v[st.top()])
			st.pop();
		int x = st.top();
		edge[x].pb(i);
		edge[i].pb(x);
		st.push(i);
	}
	stack<int>().swap(st);
	st.push(n);
	for (int i = n-1;i >= 1;--i) {
		while (st.size() && v[i] > v[st.top()])
			st.pop();
		int x = st.top();
		edge[x].pb(i);
		edge[i].pb(x);
		st.push(i);
	}
}
void bfsans(int s) {
	static int dis[maxn];
	fill(dis, dis+n+1, inf);
	dis[s] = 0;
	queue<int> togo;
	togo.push(s);
	while (togo.size()) {
		int now = togo.front();
		togo.pop();
		for (int u : edge[now]) if (dis[now]+1 < dis[u]) {
			assert(dis[u] == inf);
			dis[u] = dis[now]+1;
			togo.push(u);
		}
	}
	for (int i = 0;i < q;++i) {
		auto [x, y] = qr[i];
		res[i] = min(res[i], dis[x] + dis[y] - 1);
	}
}
random_device rd;
mt19937 gen(rd());
void solve() {
	init();
	fill(res, res+q, maxn);
//	for (int i = 0;i < q;++i)
//		bfs(i);
	vector<int> val(n);
	iota(val.begin(), val.end(), 1);
	shuffle(val.begin(), val.end(), gen);
const int SQ = 33000000 / n;	
	if (q <= 50) {
		val.clear();
		for (int i = 0;i < q;++i) 
			val.pb(qr[i].first), val.pb(qr[i].second);
		sort(val.begin(), val.end());
		val.resize(unique(val.begin(), val.end()) - val.begin());
	}
	for (int i = 0;i < min(SQ, n);++i)
		bfsans(val[i]);
}
signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k >> q;
	for (int i = 1;i <= n;++i) 
		cin >> v[i];
	for (int i = 0;i < q;++i)
		cin >> qr[i].first >> qr[i].second;
	solve();
	for (int i = 0;i < q;++i)
		cout << res[i] << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55