oj.uz

Submission #301840

# Submission time Handle Problem Language Result Execution time Memory
301840 2020-09-18T08:46:13 Z Kevin_Zhang_TW Railway Trip (JOI17_railway_trip) C++17
20 / 100
 2000 ms 9532 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 = 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.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 3 ms 2816 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2944 KB Output is correct
2 Correct 1416 ms 8192 KB Output is correct
3 Correct 1572 ms 8440 KB Output is correct
4 Correct 1688 ms 8440 KB Output is correct
5 Correct 1599 ms 8568 KB Output is correct
6 Correct 1559 ms 8568 KB Output is correct
7 Correct 1703 ms 8824 KB Output is correct
8 Correct 533 ms 7680 KB Output is correct
9 Correct 592 ms 9212 KB Output is correct
10 Correct 576 ms 8320 KB Output is correct
11 Correct 1211 ms 8696 KB Output is correct
12 Correct 1189 ms 8696 KB Output is correct
13 Correct 1190 ms 8696 KB Output is correct
14 Correct 1237 ms 8704 KB Output is correct
15 Correct 1232 ms 8696 KB Output is correct
16 Correct 1184 ms 8696 KB Output is correct
17 Correct 1849 ms 8952 KB Output is correct
18 Correct 1721 ms 8824 KB Output is correct
19 Correct 937 ms 8312 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1661 ms 9532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

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