oj.uz

Submission #29176

# Submission time Handle Problem Language Result Execution time Memory
29176 2017-07-18T14:12:10 Z khsoo01 Railway Trip (JOI17_railway_trip) C++11
45 / 100
 2000 ms 22276 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17656 KB Output is correct
2 Correct 0 ms 17656 KB Output is correct
3 Correct 0 ms 17656 KB Output is correct
4 Correct 0 ms 17656 KB Output is correct
5 Correct 0 ms 17656 KB Output is correct
6 Correct 0 ms 17656 KB Output is correct
7 Correct 0 ms 17656 KB Output is correct
8 Correct 0 ms 17656 KB Output is correct
9 Correct 0 ms 17656 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17656 KB Output is correct
2 Correct 23 ms 17656 KB Output is correct
3 Correct 23 ms 17656 KB Output is correct
4 Correct 273 ms 22012 KB Output is correct
5 Correct 273 ms 22144 KB Output is correct
6 Correct 263 ms 22144 KB Output is correct
7 Correct 246 ms 22276 KB Output is correct
8 Correct 69 ms 20824 KB Output is correct
9 Correct 73 ms 21112 KB Output is correct
10 Correct 66 ms 20984 KB Output is correct
11 Correct 176 ms 21232 KB Output is correct
12 Correct 193 ms 21368 KB Output is correct
13 Correct 183 ms 21364 KB Output is correct
14 Correct 203 ms 21232 KB Output is correct
15 Correct 183 ms 21356 KB Output is correct
16 Correct 196 ms 21364 KB Output is correct
17 Correct 269 ms 22276 KB Output is correct
18 Correct 299 ms 22276 KB Output is correct
19 Correct 153 ms 21616 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 17656 KB Output is correct
2 Correct 249 ms 17656 KB Output is correct
3 Correct 259 ms 17656 KB Output is correct
4 Correct 239 ms 17656 KB Output is correct
5 Correct 319 ms 17656 KB Output is correct
6 Correct 299 ms 17656 KB Output is correct
7 Correct 309 ms 17656 KB Output is correct
8 Correct 156 ms 17656 KB Output is correct
9 Correct 183 ms 17656 KB Output is correct
10 Correct 506 ms 17656 KB Output is correct
11 Correct 496 ms 17656 KB Output is correct
12 Correct 446 ms 17656 KB Output is correct
13 Correct 539 ms 17656 KB Output is correct
14 Correct 429 ms 17656 KB Output is correct
15 Correct 526 ms 17656 KB Output is correct
16 Correct 629 ms 17656 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 22276 KB Execution timed out
2 Halted 0 ms 0 KB -