oj.uz

Submission #29026

# Submission time Handle Problem Language Result Execution time Memory
29026 2017-07-18T06:41:17 Z 서규호(#1171) Railway Trip (JOI17_railway_trip) C++14
20 / 100
 2000 ms 10416 KB 
#include <bits/stdc++.h>
#include <unistd.h>

#define pii pair<int,int>
#define pll pair<lld,lld>
#define pb push_back
#define next nextt
#define left leftt
#define right rightt
#define lld long long
#define Inf 1000000000
#define Linf 1000000000000000000LL
#define get gett

using namespace std;

int N,K,Q;
int a[100002],d[100002];
bool check[100002];
vector<int> edge[100002];
priority_queue<pii,vector<pii>,greater<pii>> q;

void process(int x,int y){
	for(int i=1; i<=N; i++){
		d[i] = Inf;
		check[i] = false;
	}
	d[x] = 0; q.push({0,x});
	while(!q.empty()){
		int v = q.top().second;
		q.pop();
		if(check[v]) continue;
		for(auto &i : edge[v]){
			if(d[i] > d[v]+1){
				d[i] = d[v]+1;
				q.push({d[i],i});
			}
		}
	}
}

int main(){
	scanf("%d %d %d",&N,&K,&Q);
	for(int i=1; i<=N; i++){
		scanf("%d",&a[i]);
	}
	vector<pii> st;
	st.pb({K,1});
	for(int i=2; i<N; i++){
		while(st.back().first < a[i]) st.pop_back();
		edge[st.back().second].pb(i);
		edge[i].pb(st.back().second);
		st.pb({a[i],i});
	}
	st.clear();
	st.pb({K,N});
	for(int i=N-1; i>1; i--){
		while(st.back().first < a[i]) st.pop_back();
		edge[st.back().second].pb(i);
		edge[i].pb(st.back().second);
		st.pb({a[i],i});
	}
	int value = 0;
	for(int i=2; i<=N; i++){
		if(value < a[i]){
			value = a[i];
			edge[1].pb(i);
		}
	}
	value = 0;
	for(int i=N-1; i>=1; i--){
		if(value < a[i]){
			value = a[i];
			edge[N].pb(i);
		}
	}
	for(int i=1; i<=Q; i++){
		int x,y;
		scanf("%d %d",&x,&y);
		process(x,y);
		printf("%d\n",d[y]-1);
	}

	return 0;
}

Compilation message

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:43:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&N,&K,&Q);
                            ^
railway_trip.cpp:45:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^
railway_trip.cpp:79:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
                       ^

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5376 KB Output is correct
2 Correct 566 ms 9748 KB Output is correct
3 Correct 659 ms 9608 KB Output is correct
4 Correct 736 ms 9604 KB Output is correct
5 Correct 813 ms 9600 KB Output is correct
6 Correct 926 ms 9740 KB Output is correct
7 Correct 993 ms 10000 KB Output is correct
8 Correct 203 ms 9476 KB Output is correct
9 Correct 259 ms 10416 KB Output is correct
10 Correct 219 ms 10400 KB Output is correct
11 Correct 579 ms 10128 KB Output is correct
12 Correct 589 ms 10128 KB Output is correct
13 Correct 563 ms 10128 KB Output is correct
14 Correct 569 ms 10124 KB Output is correct
15 Correct 559 ms 10128 KB Output is correct
16 Correct 549 ms 10128 KB Output is correct
17 Correct 1123 ms 9996 KB Output is correct
18 Correct 1036 ms 9992 KB Output is correct
19 Correct 823 ms 9452 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 9644 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 10000 KB Execution timed out
2 Halted 0 ms 0 KB -