oj.uz

답안 #51133

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51133 2018-06-16T08:53:59 Z mirbek01 철로 (IOI14_rail) C++17
100 / 100
 134 ms 41792 KB 
#include "rail.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 2;

int n, dist[N][N], cur;

bool cmp(int a, int b){
      return dist[cur][a] < dist[cur][b];
}

void findLocation(int N, int first, int location[], int stype[]){
      location[0] = first;
      stype[0] = 1;
      if(N == 1) return ;
      vector <int> l, r, v;
      n = N;
      int in = 1;
      for(int i = 1; i < n; i ++){
            dist[0][i] = dist[i][0] = getDistance(0, i);
            if(dist[0][i] < dist[0][in]) in = i;
      }
      location[in] = first + dist[0][in];
      stype[in] = 2;
      for(int i = 1; i < n; i ++){
            if(in == i) continue;
            dist[in][i] = dist[i][in] = getDistance(in, i);
      }
      for(int i = 0; i < n; i ++){
            if(i == in) continue;
            if(i == 0 || dist[0][in] + dist[in][i] == dist[0][i])
                  l.push_back(i);
            else
                  r.push_back(i);
      }
      sort(r.begin(), r.end(), cmp);
      for(int i : r){
            bool ok = 1;
            if(!v.empty()){
                  int d = getDistance(i, v.back());
                  int pos = location[v.back()] - d;
                  if(first < pos){
                        int lo;
                        for(int j = v.size() - 1; j >= 0; j --){
                              if(location[v[j]] > pos){
                                    lo = j;
                                    int x = d - (location[v.back()] - location[v[lo]]);
                                    if(dist[0][i] == dist[0][v[lo]] + x){
                                          location[i] = location[v[lo]] - x;
                                          stype[i] = 1;
                                          ok = 0;
                                          break;
                                    }
                              }
                        }
                  }
            }
            if(ok){
                  location[i] = first + dist[0][i];
                  stype[i] = 2;
                  v.push_back(i);
            }
      }
      v.clear();
      cur = in;
      sort(l.begin(), l.end(), cmp);
      for(int i : l){
            bool ok = 1;
            if(!v.empty()){
                  int d = getDistance(i, v.back());
                  int pos = location[v.back()] + d;
                  if(pos < location[in]){
                        int lo;
                        for(int j = v.size() - 1; j >= 0; j --){
                              if(location[v[j]] < pos){
                                    lo = j;
                                    int x = d - (location[v[lo]] - location[v.back()]);
                                    if(dist[in][i] == dist[in][v[lo]] + x){
                                          location[i] = location[v[lo]] + x;
                                          stype[i] = 2;
                                          ok = 0;
                                          break;
                                    }
                              }
                        }
                  }
            }
            if(ok){
                  location[i] = location[in] - dist[in][i];
                  stype[i] = 1;
                  v.push_back(i);
            }
      }
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 924 KB Output is correct
3 Correct 2 ms 924 KB Output is correct
4 Correct 2 ms 924 KB Output is correct
5 Correct 2 ms 924 KB Output is correct
6 Correct 2 ms 924 KB Output is correct
7 Correct 2 ms 952 KB Output is correct
8 Correct 2 ms 1080 KB Output is correct
9 Correct 2 ms 1104 KB Output is correct
10 Correct 2 ms 1104 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1104 KB Output is correct
2 Correct 2 ms 1104 KB Output is correct
3 Correct 2 ms 1104 KB Output is correct
4 Correct 2 ms 1104 KB Output is correct
5 Correct 2 ms 1104 KB Output is correct
6 Correct 2 ms 1104 KB Output is correct
7 Correct 2 ms 1104 KB Output is correct
8 Correct 2 ms 1104 KB Output is correct
9 Correct 2 ms 1104 KB Output is correct
10 Correct 2 ms 1104 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 34664 KB Output is correct
2 Correct 121 ms 34664 KB Output is correct
3 Correct 134 ms 40932 KB Output is correct
4 Correct 115 ms 40932 KB Output is correct
5 Correct 116 ms 41188 KB Output is correct
6 Correct 116 ms 41188 KB Output is correct
7 Correct 113 ms 41188 KB Output is correct
8 Correct 105 ms 41188 KB Output is correct
9 Correct 116 ms 41188 KB Output is correct
10 Correct 109 ms 41188 KB Output is correct

Subtask #4
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 41188 KB Output is correct
2 Correct 108 ms 41188 KB Output is correct
3 Correct 114 ms 41188 KB Output is correct
4 Correct 113 ms 41220 KB Output is correct
5 Correct 114 ms 41264 KB Output is correct
6 Correct 113 ms 41296 KB Output is correct
7 Correct 114 ms 41296 KB Output is correct
8 Correct 107 ms 41296 KB Output is correct
9 Correct 107 ms 41296 KB Output is correct
10 Correct 103 ms 41296 KB Output is correct
11 Correct 109 ms 41296 KB Output is correct
12 Correct 111 ms 41296 KB Output is correct
13 Correct 114 ms 41664 KB Output is correct
14 Correct 112 ms 41664 KB Output is correct
15 Correct 114 ms 41748 KB Output is correct
16 Correct 115 ms 41748 KB Output is correct
17 Correct 112 ms 41792 KB Output is correct
18 Correct 112 ms 41792 KB Output is correct
19 Correct 116 ms 41792 KB Output is correct
20 Correct 103 ms 41792 KB Output is correct