oj.uz

Submission #301828

# Submission time Handle Problem Language Result Execution time Memory
301828 2020-09-18T08:38:02 Z Kevin_Zhang_TW Railway Trip (JOI17_railway_trip) C++17
5 / 100
 2000 ms 9592 KB 
#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 = 100000000 / n;	
	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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2816 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2816 KB Output is correct
2 Execution timed out 2050 ms 8192 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2054 ms 9336 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2051 ms 9592 KB Time limit exceeded
2 Halted 0 ms 0 KB -