oj.uz

Submission #49562

# Submission time Handle Problem Language Result Execution time Memory
49562 2018-05-31T09:59:15 Z khsoo01 Rail (IOI14_rail) C++11
100 / 100
 127 ms 32252 KB 
#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
const int M = 5005, inf = 1e9;

int d[M][M];

map<int,int> inv;

int getd (int I, int J) {
	if(I == J) return 0;
	if(I > J) swap(I, J);
	if(!d[I][J]) d[I][J] = getDistance(I, J);
	return d[I][J];
}

void solve (int L[], int S[], vector<int> &X, int P, int Q) {
	sort(X.begin(), X.end(),
		[&](int A, int B) {
			return getd(P, A) < getd(P, B);
		});
	int D = 1 - 2 * (S[P] == 1);
	for(auto &T : X) {
		int V = (getd(Q, T) + getd(P, Q) - getd(P, T)) / 2;
		int C = L[Q] + D * V;
		if(inv[C] == S[Q]) {
			L[T] = C + D * (getd(P, T) - abs(L[P] - C));
			S[T] = S[P];
		}
		else {
			L[T] = L[P] - D * getd(P, T);
			S[T] = S[Q];
			Q = T;
		}
		inv[L[T]] = S[T];
	}
}

void findLocation(int N, int F, int L[], int S[])
{
	L[0] = F;
	S[0] = 1;
	inv[L[0]] = 1;
	if(N == 1) return;
	int I = 1;
	for(int i=2;i<N;i++) {
		if(getd(0, I) > getd(0, i)) I = i;
	}
	L[I] = L[0] + getd(0, I);
	S[I] = 2;
	inv[L[I]] = 2;
	vector<int> X, Y;
	for(int i=1;i<N;i++) {
		if(i == I) continue;
		if(getd(I, i) + getd(I, 0) == getd(0, i)) {
			if(getd(I, 0) > getd(I, i)) {
				L[i] = L[0] + getd(I, 0) - getd(I, i);
				S[i] = 1;
				inv[L[i]] = 1;
			}
			else X.push_back(i);
		}
		else Y.push_back(i);
	}
	solve(L, S, X, I, 0);
	solve(L, S, Y, 0, I);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 3 ms 748 KB Output is correct
5 Correct 3 ms 816 KB Output is correct
6 Correct 3 ms 816 KB Output is correct
7 Correct 3 ms 816 KB Output is correct
8 Correct 3 ms 816 KB Output is correct
9 Correct 2 ms 928 KB Output is correct
10 Correct 2 ms 936 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 936 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 3 ms 980 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 3 ms 980 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 3 ms 1004 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 20336 KB Output is correct
2 Correct 116 ms 20336 KB Output is correct
3 Correct 127 ms 22908 KB Output is correct
4 Correct 115 ms 22908 KB Output is correct
5 Correct 117 ms 22908 KB Output is correct
6 Correct 121 ms 24512 KB Output is correct
7 Correct 120 ms 28540 KB Output is correct
8 Correct 120 ms 30592 KB Output is correct
9 Correct 115 ms 30592 KB Output is correct
10 Correct 126 ms 32252 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 32252 KB Output is correct
2 Correct 109 ms 32252 KB Output is correct
3 Correct 113 ms 32252 KB Output is correct
4 Correct 113 ms 32252 KB Output is correct
5 Correct 122 ms 32252 KB Output is correct
6 Correct 120 ms 32252 KB Output is correct
7 Correct 126 ms 32252 KB Output is correct
8 Correct 122 ms 32252 KB Output is correct
9 Correct 111 ms 32252 KB Output is correct
10 Correct 120 ms 32252 KB Output is correct
11 Correct 120 ms 32252 KB Output is correct
12 Correct 111 ms 32252 KB Output is correct
13 Correct 117 ms 32252 KB Output is correct
14 Correct 111 ms 32252 KB Output is correct
15 Correct 118 ms 32252 KB Output is correct
16 Correct 114 ms 32252 KB Output is correct
17 Correct 113 ms 32252 KB Output is correct
18 Correct 121 ms 32252 KB Output is correct
19 Correct 119 ms 32252 KB Output is correct
20 Correct 113 ms 32252 KB Output is correct