Submission #201573

#	Time	Username	Problem	Language	Result	Execution time	Memory
201573		arnold518	Railway Trip (JOI17_railway_trip)	C++14	20 / 100	2069 ms	9700 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, K, Q, A[MAXN+10];
vector<pii> E;
vector<int> adj[MAXN+10];

int dist[MAXN+10];

int main()
{
	int i, j;

	scanf("%d%d%d", &N, &K, &Q);
	for(i=1; i<=N; i++) scanf("%d", &A[i]);

	vector<int> S;

	S.clear(); S.push_back(1);
	for(i=2; i<=N; i++)
	{
		while(!S.empty() && A[S.back()]<A[i]) S.pop_back();
		E.push_back({S.back(), i});
		S.push_back(i);
	}

	S.clear(); S.push_back(N);
	for(i=N-1; i>=1; i--)
	{
		while(!S.empty() && A[S.back()]<A[i]) S.pop_back();
		E.push_back({i, S.back()});
		S.push_back(i);
	}

	sort(E.begin(), E.end());
	E.erase(unique(E.begin(), E.end()), E.end());

	for(auto it : E) adj[it.first].push_back(it.second), adj[it.second].push_back(it.first);

	while(Q--)
	{
		int x, y;
		scanf("%d%d", &x, &y);

		memset(dist, -1, sizeof(dist));
		queue<int> Q;
		Q.push(x); dist[x]=0;
		while(!Q.empty())
		{
			int now=Q.front(); Q.pop();
			for(auto nxt : adj[now])
			{
				if(dist[nxt]!=-1) continue;
				Q.push(nxt); dist[nxt]=dist[now]+1;
			}
		}
		printf("%d\n", dist[y]-1);
	}
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:20:7: 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:21:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d", &A[i]);
                      ~~~~~^~~~~~~~~~~~~
railway_trip.cpp:49:8: 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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55