oj.uz

Submission #425297

# Submission time Handle Problem Language Result Execution time Memory
425297 2021-06-12T19:39:07 Z MarcoMeijer Rail (IOI14_rail) C++14
100 / 100
 192 ms 118140 KB 
#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<ii> vii;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define FOR(a,b) for(auto& a : b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(),a.end()

const int MX = 6000;

int mem[MX][MX];

void findLocation(int n, int first, int location[], int stype[]) {
  RE(i,n) RE(j,n) mem[i][j] = -1;
  auto getD = [&](int u, int v) {
    if(u == v) return 0;
    if(mem[u][v] != -1)
      return mem[u][v];
    return mem[u][v] = mem[v][u] = getDistance(u,v);
  };

  RE(i,n) location[i] = -1;

  int closest = 1e9;
  REP(i,1,n)
    closest = min(closest, getD(0,i));
  
  int u = -1;
  REP(i,1,n)
    if(getD(0,i) == closest)
      u = i;
  
  stype   [0] = 1;
  location[0] = first;
  stype   [u] = 2;
  location[u] = first + getD(0,u);

  vii pql, pqr;
  REP(i,1,n) {
    if(i == u) continue;
    int d0 = getD(i,0);
    int du = getD(i,u);
    if(getD(0,u) + du == d0 && du < getD(0,u)) {
      stype   [i] = 1;
      location[i] = location[u] - du;
    } else if(getD(0,u) + du == d0) {
      pql.pb({du,i});
    } else {
      pqr.pb({d0,i});
    }
  }
  sort(all(pql));
  sort(all(pqr));

  int x = u;
  FOR(p,pqr) {
    int i = p.se;
    int z = getD(0,x) + getD(x,i) - getD(0,i);
    z /= 2;
    int type = 1;
    RE(j,n)
      if(location[j] == location[x] - z)
        type = stype[j];
    if(type == 1) {
      location[i] = location[0] + getD(0,i);
      stype   [i] = 2;
      x = i;
    } else {
      location[i] = location[x] - getD(x,i);
      stype   [i] = 1;
    }
  }

  x = 0;
  FOR(p,pql) {
    int i = p.se;
    int z = getD(u,x) + getD(x,i) - getD(u,i);
    z /= 2;
    int type = 2;
    RE(j,n)
      if(location[j] == location[x] + z)
        type = stype[j];
    if(type == 2) {
      location[i] = location[u] - getD(u,i);
      stype   [i] = 1;
      x = i;
    } else {
      location[i] = location[x] + getD(x,i);
      stype   [i] = 2;
    }
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 756 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 756 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 716 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 760 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 764 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 716 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 117956 KB Output is correct
2 Correct 171 ms 118000 KB Output is correct
3 Correct 181 ms 117956 KB Output is correct
4 Correct 172 ms 117956 KB Output is correct
5 Correct 166 ms 118140 KB Output is correct
6 Correct 168 ms 117992 KB Output is correct
7 Correct 174 ms 117884 KB Output is correct
8 Correct 178 ms 117888 KB Output is correct
9 Correct 167 ms 117884 KB Output is correct
10 Correct 170 ms 117876 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 117876 KB Output is correct
2 Correct 179 ms 118004 KB Output is correct
3 Correct 166 ms 117892 KB Output is correct
4 Correct 171 ms 117888 KB Output is correct
5 Correct 178 ms 118084 KB Output is correct
6 Correct 169 ms 118004 KB Output is correct
7 Correct 175 ms 117968 KB Output is correct
8 Correct 173 ms 117880 KB Output is correct
9 Correct 192 ms 117884 KB Output is correct
10 Correct 168 ms 117880 KB Output is correct
11 Correct 170 ms 117876 KB Output is correct
12 Correct 169 ms 117872 KB Output is correct
13 Correct 180 ms 117872 KB Output is correct
14 Correct 171 ms 117888 KB Output is correct
15 Correct 167 ms 117956 KB Output is correct
16 Correct 170 ms 117888 KB Output is correct
17 Correct 192 ms 118020 KB Output is correct
18 Correct 169 ms 117980 KB Output is correct
19 Correct 174 ms 117956 KB Output is correct
20 Correct 169 ms 117892 KB Output is correct