Submission #126555

#	Time	Username	Problem	Language	Result	Execution time	Memory
126555		briansu	Railway Trip (JOI17_railway_trip)	C++14	20 / 100	2061 ms	10956 KiB

railway_trip

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#define REP(i, n) for(int i = 0;i < n;i ++)
#define REP1(i, n) for(int i = 1;i <= n;i ++)
#define FILL(i, n) memset(i, n, sizeof(i))
#define X first
#define Y second
#define pb push_back
#define SZ(_a) ((int)(_a).size())
#define ALL(_a) (_a).begin(), (_a).end()
#ifdef brian
#define IOS() 
template<typename T>void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...t>void _do(T &&x, t &&...X){cerr<<x<<", ";_do(X...);}
#define debug(...) {\
	fprintf(stderr, "%s - %d (%s) = ", __PRETTY_FUNCTION__, __LINE__, #__VA_ARGS__);\
	_do(__VA_ARGS__);\
}
#else
#define debug(...)
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#endif

const ll MAXn = 1e5 + 5;
const ll INF = ll(1e18);
const ll MOD = 1000000007;

ll d[MAXn], dis[MAXn], tdis[MAXn];

vector<ii> v[MAXn];
ll n, k, q;

void dijk(int s)
{
	REP1(i, n)dis[i] = INF;
	dis[s] = 0;
	priority_queue<ii, vector<ii>, greater<ii>> pq;
	pq.push(ii(0, s));
	while(SZ(pq))
	{
		while(SZ(pq) && dis[pq.top().Y] != pq.top().X)pq.pop();
		if(!SZ(pq))break;
		ll t = pq.top().Y;pq.pop();
		debug(t);
		for(auto &p:v[t])debug(t, p.X, p.Y, dis[p.X]);
		for(auto &p:v[t])if(dis[p.X] > dis[t] + p.Y)
		{
			debug(t, p.X);
			dis[p.X] = dis[t] + p.Y;
			pq.push(ii(dis[p.X], p.X));
		}
	}
	debug(s);
	REP1(i, n)debug(i, dis[i]);
}

int main(){
	IOS();
	cin>>n>>k>>q;
	REP1(i, n)cin>>d[i];

	{
		vector<ll> stk;
		REP1(i, n)
		{
			while(SZ(stk) && d[stk.back()] < d[i])stk.pop_back();
			if(SZ(stk))v[i].pb(ii(stk.back(), 1));
			stk.pb(i);
		}
	}
	{
		vector<ll> stk;
		for(int i = n;i > 0;i --)
		{
			while(SZ(stk) && d[stk.back()] < d[i])stk.pop_back();
			if(SZ(stk))v[i].pb(ii(stk.back(), 1));
			stk.pb(i);
		}
	}
	REP1(i, n)for(auto &p:v[i])debug(i, p.X, p.Y);
	while(q--)
	{
		ll a, b;
		cin>>a>>b;
		dijk(a);

		REP1(i, n)tdis[i] = dis[i];
		dijk(b);
		ll ans = INF;
		REP1(i, n)ans = min(ans, tdis[i] + dis[i] - 1);
		cout<<ans<<endl;
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55