Submission #72713

#	Time	Username	Problem	Language	Result	Execution time	Memory
72713		ikura355	Railway Trip (JOI17_railway_trip)	C++14	5 / 100	4 ms	560 KiB

railway_trip

#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 (stderr)

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 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55