Submission #29176

#	Time	Username	Problem	Language	Result	Execution time	Memory
29176		khsoo01	Railway Trip (JOI17_railway_trip)	C++11	45 / 100	2000 ms	22276 KiB

railway_trip

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;
const int N = 100005, K = 25, inf = 1e9;

int n, p, k, ts, a[N];

int sum[N][K], d[N], da[N], db[N], vis[N];
pii l[N], r[N];

vector<pii> st, sa[K], sb[K];

priority_queue<pii> pq;

void upd (int D[], int I, int V) {
	if(!I) return;
	if(vis[I] != ts || D[I] > V) {
		vis[I] = ts; D[I] = V;
		pq.push({-D[I], I});
	}
}

void solve1() {
	for(int i=1;i<=n;i++) {
		sum[i][a[i]]++;
		for(int j=1;j<=k;j++) {
			sum[i][j] += sum[i-1][j];
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=k;j>=1;j--) {
			sum[i][j] += sum[i][j+1];
		}
	}
	st.push_back(pii(0, inf));
	for(int i=1;i<=n;i++) {
		while(st.back().Y < a[i]) st.pop_back();
		int I = st.back().X;
		if(st.back().Y == a[i]) {
			l[i] = pii(l[I].X, l[I].Y+1);
			st.pop_back();
		}
		else l[i] = pii(I, 1);
		st.push_back(pii(i, a[i]));
	}
	st.clear();
	st.push_back(pii(0, inf));
	for(int i=n;i>=1;i--) {
		while(st.back().Y < a[i]) st.pop_back();
		int I = st.back().X;
		if(st.back().Y == a[i]) {
			r[i] = pii(r[I].X, r[I].Y+1);
			st.pop_back();
		}
		else r[i] = pii(I, 1);
		st.push_back(pii(i, a[i]));
	}
	st.clear();
	while(p--) {
		int A, B;
		scanf("%d%d",&A,&B);
		for(int i=1;i<=k;i++) {
			sa[i].clear(); sb[i].clear();
		}
		da[A] = 0; vis[A] = ++ts; pq.push({0, A});
		while(!pq.empty()) {
			auto T = pq.top(); pq.pop();
			int X, Y; tie(X, Y) = T; X *= -1;
			if(da[Y] != X) continue;
			sa[a[Y]].push_back({Y, X});
			upd(da, l[Y].X, X + l[Y].Y);
			upd(da, r[Y].X, X + r[Y].Y);
		}
		db[B] = 0; vis[B] = ++ts; pq.push({0, B});
		while(!pq.empty()) {
			auto T = pq.top(); pq.pop();
			int X, Y; tie(X, Y) = T; X *= -1;
			if(db[Y] != X) continue;
			sb[a[Y]].push_back({Y, X});
			upd(db, l[Y].X, X + l[Y].Y);
			upd(db, r[Y].X, X + r[Y].Y);
		}
		int ans = inf;
		for(int i=1;i<=k;i++) {
			for(auto &X : sa[i]) for(auto &Y : sb[i]) {
				int X1, X2, Y1, Y2;
				tie(X1, X2) = X; tie(Y1, Y2) = Y;
				if(X1 > Y1) {swap(X1, Y1); swap(X2, Y2);}
				ans = min(ans, X2 + Y2 + sum[Y1][i] - sum[X1][i]);
			}
		}
		printf("%d\n",ans-1);
	}
}

vector<int> adj[N];

queue<int> q;

void solve2() {
	st.push_back({0, inf});
	for(int i=1;i<=n;i++) {
		while(st.back().Y < a[i]) {
			adj[i].push_back(st.back().X);
			st.pop_back();
		}
		adj[i].push_back(st.back().X);
		if(st.back().Y == a[i]) st.pop_back();
		st.push_back(pii(i, a[i]));
	}
	st.clear();
	st.push_back({0, inf});
	for(int i=n;i>=1;i--) {
		while(st.back().Y < a[i]) {
			adj[i].push_back(st.back().X);
			st.pop_back();
		}
		adj[i].push_back(st.back().X);
		if(st.back().Y == a[i]) st.pop_back();
		st.push_back(pii(i, a[i]));
	}
	while(p--) {
		int A, B;
		scanf("%d%d",&A,&B);
		for(int i=1;i<=n;i++) d[i] = inf;
		d[A] = 0; q.push(A);
		while(!q.empty()) {
			int C = q.front(); q.pop();
			for(auto &T : adj[C]) {
				if(d[T] > d[C] + 1) {
					d[T] = d[C] + 1;
					q.push(T);
				}
			}
		}
		printf("%d\n",d[B]-1);
	}
}

int main()
{
	scanf("%d%d%d",&n,&k,&p);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	if(k <= 20) solve1();
	else solve2();
}

Compilation message (stderr)

railway_trip.cpp: In function 'void solve1()':
railway_trip.cpp:63:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
                      ^
railway_trip.cpp: In function 'void solve2()':
railway_trip.cpp:126:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
                      ^
railway_trip.cpp: In function 'int main()':
railway_trip.cpp:144:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&k,&p);
                          ^
railway_trip.cpp:145:41: 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]);
                                         ^

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