oj.uz

Submission #335277

# Submission time Handle Problem Language Result Execution time Memory
335277 2020-12-11T19:27:08 Z Plurm Railway Trip (JOI17_railway_trip) C++11
15 / 100
 2000 ms 12644 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 5 ms 4972 KB Output is correct
8 Correct 4 ms 4972 KB Output is correct
9 Runtime error 10 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 6 ms 5100 KB Output is correct
2 Correct 387 ms 9196 KB Output is correct
3 Correct 453 ms 9316 KB Output is correct
4 Correct 487 ms 9188 KB Output is correct
5 Correct 501 ms 9068 KB Output is correct
6 Correct 549 ms 9160 KB Output is correct
7 Correct 1146 ms 10748 KB Output is correct
8 Correct 181 ms 9740 KB Output is correct
9 Correct 188 ms 10348 KB Output is correct
10 Correct 163 ms 10088 KB Output is correct
11 Correct 478 ms 10084 KB Output is correct
12 Correct 467 ms 9708 KB Output is correct
13 Correct 463 ms 9580 KB Output is correct
14 Correct 475 ms 9964 KB Output is correct
15 Correct 481 ms 9708 KB Output is correct
16 Correct 470 ms 9700 KB Output is correct
17 Correct 479 ms 9068 KB Output is correct
18 Correct 482 ms 9188 KB Output is correct
19 Correct 366 ms 12644 KB Output is correct

Subtask #3
0 / 25.0

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