oj.uz

Submission #335278

# Submission time Handle Problem Language Result Execution time Memory
335278 2020-12-11T19:30:26 Z Plurm Railway Trip (JOI17_railway_trip) C++11
15 / 100
 2000 ms 12524 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> g[100005]; // cartesian-tree-like graph
int d[100005];
vector<int> bckt[100005];
int l[100005];
int n,k,q;
void compute(int a){
	d[a] = 0;
	for(int i = 1; i <= k; i++){
		for(int x : bckt[i]){
			for(int y : g[x]) d[x] = min(d[x], d[y]+1);
		}
		reverse(bckt[i].begin(), bckt[i].end());
		for(int x : bckt[i]){
			for(int y : g[x]) d[x] = min(d[x], d[y]+1);
		}
		reverse(bckt[i].begin(), bckt[i].end());
	}
}
int main(){
	scanf("%d%d%d",&n,&k,&q);
	stack<int> stk;
	for(int i = 1; i <= n; i++){
		scanf("%d", l+i);
		bckt[l[i]].push_back(i);
		while(!stk.empty() && l[stk.top()] <= l[i]){
			g[i].push_back(stk.top());
			stk.pop();
		}
		if(!stk.empty() && l[stk.top()] == l[i]) g[i].push_back(stk.top());
		stk.push(i);
	}
	while(!stk.empty()) stk.pop();
	for(int i = n; i > 0; i--){
		while(!stk.empty() && l[stk.top()] <= l[i]){
			g[i].push_back(stk.top());
			stk.pop();
		}
		if(!stk.empty() && l[stk.top()] == l[i]) g[i].push_back(stk.top());
		stk.push(i);
	}
	while(q--){
		int a,b;
		scanf("%d%d",&a,&b);
		for(int i = 1; i <= n; i++) d[i] = 1e9;
		compute(a);
		vector<int> v(n);
		for(int i = 1; i <= n; i++) v[i] = d[i];
		for(int i = 1; i <= n; i++) d[i] = 1e9;
		compute(b);
		int ans = 1e9;
		for(int i = 1; i <= n; i++){
			ans = min(ans, v[i] + d[i]);
		}
		printf("%d\n", ans-1);
	}
	return 0;
}

Compilation message

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |  scanf("%d%d%d",&n,&k,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
railway_trip.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |   scanf("%d", l+i);
      |   ~~~~~^~~~~~~~~~~
railway_trip.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 4972 KB Output is correct
5 Correct 4 ms 4972 KB Output is correct
6 Correct 4 ms 4972 KB Output is correct
7 Correct 4 ms 4972 KB Output is correct
8 Correct 4 ms 4972 KB Output is correct
9 Runtime error 12 ms 9964 KB Execution killed with signal 6 (could be triggered by violating memory limits)

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5100 KB Output is correct
2 Correct 387 ms 9324 KB Output is correct
3 Correct 453 ms 9324 KB Output is correct
4 Correct 505 ms 9068 KB Output is correct
5 Correct 544 ms 9068 KB Output is correct
6 Correct 567 ms 9068 KB Output is correct
7 Correct 1211 ms 10724 KB Output is correct
8 Correct 178 ms 9700 KB Output is correct
9 Correct 187 ms 10348 KB Output is correct
10 Correct 162 ms 10088 KB Output is correct
11 Correct 478 ms 10260 KB Output is correct
12 Correct 448 ms 9828 KB Output is correct
13 Correct 467 ms 9700 KB Output is correct
14 Correct 467 ms 9964 KB Output is correct
15 Correct 473 ms 9960 KB Output is correct
16 Correct 482 ms 9628 KB Output is correct
17 Correct 479 ms 9068 KB Output is correct
18 Correct 484 ms 9068 KB Output is correct
19 Correct 364 ms 12524 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2066 ms 9068 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 2065 ms 10596 KB Time limit exceeded
2 Halted 0 ms 0 KB -