oj.uz

답안 #72713

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72713 2018-08-26T18:59:49 Z ikura355 Railway Trip (JOI17_railway_trip) C++14
5 / 100
 4 ms 560 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 5;
const int inf = 1e9;

int n,k,m;
int a[maxn];
int st[maxn], ft[maxn];

int dq[maxn];
int len1[maxn], len2[maxn];
vector<int> way[maxn];
queue<int> q;

void init() {
	int sz = 0;
	for(int x=1;x<=n;x++) {
		int l = 1, r = sz, mid, pos = -1;
		while(l<=r) {
			mid = (l+r)/2;
			if(a[x] <= a[dq[mid]]) {
				pos = dq[mid];
				l = mid+1;
			}
			else r = mid-1;
		}
		if(pos!=-1) {
			way[x].push_back(pos);
//			printf("%d - %d\n",x,pos);
		}
		dq[++sz] = x;
		while(sz>=2 && a[dq[sz-1]] <= a[dq[sz]]) dq[sz-1] = dq[sz], sz--;
	}
	sz = 0;
	for(int x=n;x>=1;x--) {
		int l = 1, r = sz, mid, pos = -1;
		while(l<=r) {
			mid = (l+r)/2;
			if(a[x] <= a[dq[mid]]) {
				pos = dq[mid];
				l = mid+1;
			}
			else r = mid-1;
		}
		if(pos!=-1) {
			way[x].push_back(pos);
//			printf("%d - %d\n",x,pos);
		}
		dq[++sz] = x;
		while(sz>=2 && a[dq[sz-1]] <= a[dq[sz]]) dq[sz-1] = dq[sz], sz--;
	}
}

int solve(int x, int y) {
	for(int i=1;i<=n;i++) len1[i] = len2[i] = inf;
	len1[x] = 0;
	q.push(x);
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(auto v : way[u]) {
			if(len1[v] > len1[u] + 1) {
				len1[v] = len1[u] + 1;
				q.push(v);
			}
		}
	}
	len2[y] = 0;
	q.push(y);
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(auto v : way[u]) {
			if(len2[v] > len2[u] + 1) {
				len2[v] = len2[u] + 1;
				q.push(v);
			}
		}
	}
	int ans = inf;
	for(int i=1;i<=n;i++) {
		ans = min(ans, len1[i] + len2[i] - 1);
	}
	return ans;
}

int main() {
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) scanf("%d%d",&st[i],&ft[i]);
	init();
	for(int i=1;i<=m;i++) printf("%d\n",solve(st[i],ft[i]));
}

Compilation message

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&k,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~
railway_trip.cpp:88:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
                        ~~~~~^~~~~~~~~~~~
railway_trip.cpp:89:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%d%d",&st[i],&ft[i]);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 2 ms 544 KB Output is correct
7 Correct 2 ms 544 KB Output is correct
8 Correct 3 ms 544 KB Output is correct
9 Correct 3 ms 544 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 544 KB Output is correct
2 Incorrect 2 ms 544 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4 ms 560 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -