oj.uz

Submission #55065

# Submission time Handle Problem Language Result Execution time Memory
55065 2018-07-06T00:18:29 Z ksun48 Railway Trip (JOI17_railway_trip) C++14
25 / 100
 2000 ms 26476 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main(){
	cin.sync_with_stdio(0); cin.tie(0);
	int next[2][100000][20]; // next stop of level <= j, you are <= j+1 (taking trains of j+1)
	int idx[100000][21];
	//int next[2][1000][20]; // next stop of level <= j, you are <= j+1 (taking trains of j+1)
	//int idx[1000][21];
	int n, k, q;
	cin >> n >> k >> q;
	vector<int> level(n);
	for(int i = 0; i < n; i++){
		cin >> level[i];
		level[i] = k - level[i];
	}
	vector<pair<int,int> > queries;
	for(int i = 0; i < q; i++){
		int a, b;
		cin >> a >> b;
		a--; b--;
		queries.push_back({a,b});
	}
	for(int j = 0; j <= k; j++){
		int cur = 0;
		for(int i = 0; i < n; i++){
			if(level[i] <= j){
				idx[i][j] = cur;
				cur++;
			}
		}
	}
	for(int j = 0; j < k; j++){
		int prev = 0;
		for(int i = 0; i < n; i++){
			if(level[i] > j+1) continue;
			if(level[i] <= j){
				prev = i;
			}
			next[0][i][j] = prev;
		}
		prev = n-1;
		for(int i = n-1; i >= 0; i--){
			if(level[i] > j+1) continue;
			if(level[i] <= j){
				prev = i;
			}
			next[1][i][j] = prev;
		}
	}
	for(int zz = 0; zz < queries.size(); zz++){
		pair<int,int> stuff[2][2]; // person, then side
		stuff[0][0] = stuff[0][1] = {queries[zz].first, 0};
		stuff[1][0] = stuff[1][1] = {queries[zz].second, 0};
		int ans = 1000000000;
		for(int j = k-1; j >= 0; j--){
			// go to level j
			for(int p = 0; p < 2; p++){
				pair<int,int> newstuff[2];
				newstuff[0] = make_pair(next[0][stuff[p][0].first ][j], 1000000000);
				newstuff[1] = make_pair(next[1][stuff[p][1].first ][j], 1000000000);
				for(int i = 0; i < 2; i++){
					pair<int,int> x = stuff[p][i];
					// go left from x, go right from x;
					int loc = x.first;
					int dist = x.second;
					for(int dir = 0; dir < 2; dir++){
						int newloc = next[dir][loc][j];
						int newdist = dist + abs(idx[ loc ][j+1] - idx[ newloc ][j+1]);
						for(int qq = 0; qq < 2; qq++){
							if(newstuff[qq].first == newloc){
								newstuff[qq].second = min(newstuff[qq].second, newdist);
							}
						}
					}
				}
				stuff[p][0] = newstuff[0];
				stuff[p][1] = newstuff[1];
			}
			// find ans
			for(int i0 = 0; i0 < 2; i0++){
				pair<int,int> x0 = stuff[0][i0];
				for(int i1 = 0; i1 < 2; i1++){
					pair<int,int> x1 = stuff[1][i1];
					ans = min(ans, x0.second + x1.second + abs(idx[x0.first][j] - idx[x1.first][j]));
				}
			}
		}
		cout << ans - 1 << '\n';
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 26196 KB Output is correct
2 Correct 239 ms 26228 KB Output is correct
3 Correct 308 ms 26228 KB Output is correct
4 Correct 310 ms 26348 KB Output is correct
5 Correct 342 ms 26348 KB Output is correct
6 Correct 344 ms 26348 KB Output is correct
7 Correct 357 ms 26348 KB Output is correct
8 Correct 112 ms 26348 KB Output is correct
9 Correct 162 ms 26396 KB Output is correct
10 Correct 189 ms 26396 KB Output is correct
11 Correct 207 ms 26476 KB Output is correct
12 Correct 189 ms 26476 KB Output is correct
13 Correct 193 ms 26476 KB Output is correct
14 Correct 220 ms 26476 KB Output is correct
15 Correct 225 ms 26476 KB Output is correct
16 Correct 459 ms 26476 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 26476 KB Time limit exceeded
2 Halted 0 ms 0 KB -