Submission #49562

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
49562	2018-05-31 09:59:15	khsoo01	Rail (IOI14_rail)	C++11	100 / 100	127 ms	32252 KiB

rail

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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 {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44