oj.uz

Submission #335276

# Submission time Handle Problem Language Result Execution time Memory
335276 2020-12-11T19:25:58 Z Plurm Railway Trip (JOI17_railway_trip) C++11
15 / 100
 2000 ms 13036 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);
		memset(d, 0x3f, sizeof(d));
		compute(a);
		vector<int> v(n);
		for(int i = 1; i <= n; i++) v[i] = d[i];
		memset(d, 0x3f, sizeof(d));
		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 6 ms 5376 KB Output is correct
2 Correct 5 ms 5356 KB Output is correct
3 Correct 5 ms 5356 KB Output is correct
4 Correct 6 ms 5356 KB Output is correct
5 Correct 5 ms 5356 KB Output is correct
6 Correct 6 ms 5356 KB Output is correct
7 Correct 6 ms 5356 KB Output is correct
8 Correct 6 ms 5356 KB Output is correct
9 Runtime error 11 ms 10872 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 8 ms 5484 KB Output is correct
2 Correct 426 ms 9440 KB Output is correct
3 Correct 462 ms 9456 KB Output is correct
4 Correct 546 ms 9324 KB Output is correct
5 Correct 552 ms 9452 KB Output is correct
6 Correct 564 ms 9572 KB Output is correct
7 Correct 1205 ms 11116 KB Output is correct
8 Correct 185 ms 9956 KB Output is correct
9 Correct 196 ms 10988 KB Output is correct
10 Correct 163 ms 10472 KB Output is correct
11 Correct 474 ms 10596 KB Output is correct
12 Correct 478 ms 10348 KB Output is correct
13 Correct 465 ms 10212 KB Output is correct
14 Correct 509 ms 10596 KB Output is correct
15 Correct 454 ms 10348 KB Output is correct
16 Correct 495 ms 10092 KB Output is correct
17 Correct 486 ms 9700 KB Output is correct
18 Correct 483 ms 9708 KB Output is correct
19 Correct 374 ms 13036 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2098 ms 9452 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 2085 ms 11364 KB Time limit exceeded
2 Halted 0 ms 0 KB -