oj.uz

Submission #1077490

# Submission time Handle Problem Language Result Execution time Memory
1077490 2024-08-27T07:41:03 Z juicy Stations (IOI20_stations) C++17
100 / 100
 692 ms 1188 KB 
#include "stations.h"

#include <bits/stdc++.h>

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
  std::vector<std::vector<int>> g(n);
  for (int i = 0; i < n - 1; ++i) {
    g[u[i]].push_back(v[i]);
    g[v[i]].push_back(u[i]);
  }
  std::vector<int> lab(n), tin(n), tout(n);
  std::function<void(int, int, int)> dfs = [&](int u, int p, int dep) {
    static int timer = 0;
    tin[u] = ++timer;
    for (int v : g[u]) {
      if (v ^ p) {
        dfs(v, u, dep + 1);
      }
    }
    tout[u] = ++timer;
    lab[u] = dep & 1 ? tout[u] : tin[u];
  };
  dfs(0, 0, 0);
  std::vector<int> ord(n); iota(ord.begin(), ord.end(), 0);
  std::sort(ord.begin(), ord.end(), [&](int u, int v) {
    return lab[u] < lab[v];
  });
  for (int i = 0; i < n; ++i) {
    lab[ord[i]] = i;
  }
  return lab;
}

std::array<int, 3> qry(int u, std::vector<int> &c) {
  if (c.size() == 1) {
    return {c[0], u, u};
  }
  if (u <= c[0]) {
    int pr = c.back(); c.pop_back();
    return {pr, u, c.back()};
  }
  int pr = c[0]; c.erase(c.begin());
  return {pr, c[0], u};
}

int find_next_station(int s, int t, std::vector<int> c) {
  auto [pr, l, r] = qry(s, c);
  if (l <= t && t <= r) {
    bool f = pr < s;
    int lst = -1;
    for (int x : c) {
      if (f && x > t) {
        return lst;
      }
      if (!f && t <= x) {
        return x;
      }
      lst = x;
    }
    return lst;
  } 
  return pr;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 940 KB Output is correct
2 Correct 300 ms 940 KB Output is correct
3 Correct 565 ms 684 KB Output is correct
4 Correct 429 ms 684 KB Output is correct
5 Correct 329 ms 692 KB Output is correct
6 Correct 263 ms 776 KB Output is correct
7 Correct 280 ms 772 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 3 ms 1020 KB Output is correct
10 Correct 2 ms 768 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 772 KB Output is correct
2 Correct 353 ms 772 KB Output is correct
3 Correct 627 ms 684 KB Output is correct
4 Correct 431 ms 684 KB Output is correct
5 Correct 402 ms 684 KB Output is correct
6 Correct 330 ms 684 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 940 KB Output is correct
2 Correct 297 ms 940 KB Output is correct
3 Correct 542 ms 684 KB Output is correct
4 Correct 423 ms 684 KB Output is correct
5 Correct 368 ms 684 KB Output is correct
6 Correct 321 ms 956 KB Output is correct
7 Correct 278 ms 940 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 1 ms 764 KB Output is correct
10 Correct 0 ms 768 KB Output is correct
11 Correct 420 ms 684 KB Output is correct
12 Correct 307 ms 1188 KB Output is correct
13 Correct 338 ms 1016 KB Output is correct
14 Correct 302 ms 684 KB Output is correct
15 Correct 25 ms 768 KB Output is correct
16 Correct 44 ms 684 KB Output is correct
17 Correct 61 ms 684 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 684 KB Output is correct
2 Correct 454 ms 684 KB Output is correct
3 Correct 393 ms 684 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 2 ms 776 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 388 ms 684 KB Output is correct
8 Correct 581 ms 684 KB Output is correct
9 Correct 470 ms 684 KB Output is correct
10 Correct 405 ms 684 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 2 ms 768 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 0 ms 768 KB Output is correct
16 Correct 402 ms 684 KB Output is correct
17 Correct 330 ms 684 KB Output is correct
18 Correct 345 ms 684 KB Output is correct
19 Correct 365 ms 684 KB Output is correct
20 Correct 380 ms 684 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 940 KB Output is correct
2 Correct 317 ms 940 KB Output is correct
3 Correct 631 ms 684 KB Output is correct
4 Correct 448 ms 684 KB Output is correct
5 Correct 440 ms 684 KB Output is correct
6 Correct 288 ms 940 KB Output is correct
7 Correct 368 ms 684 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 330 ms 684 KB Output is correct
12 Correct 353 ms 684 KB Output is correct
13 Correct 692 ms 684 KB Output is correct
14 Correct 508 ms 684 KB Output is correct
15 Correct 379 ms 684 KB Output is correct
16 Correct 316 ms 936 KB Output is correct
17 Correct 428 ms 684 KB Output is correct
18 Correct 335 ms 764 KB Output is correct
19 Correct 292 ms 1016 KB Output is correct
20 Correct 302 ms 684 KB Output is correct
21 Correct 31 ms 764 KB Output is correct
22 Correct 50 ms 940 KB Output is correct
23 Correct 79 ms 1028 KB Output is correct
24 Correct 4 ms 764 KB Output is correct
25 Correct 3 ms 764 KB Output is correct
26 Correct 4 ms 768 KB Output is correct
27 Correct 2 ms 768 KB Output is correct
28 Correct 1 ms 764 KB Output is correct
29 Correct 358 ms 684 KB Output is correct
30 Correct 345 ms 684 KB Output is correct
31 Correct 294 ms 684 KB Output is correct
32 Correct 362 ms 684 KB Output is correct
33 Correct 284 ms 684 KB Output is correct
34 Correct 223 ms 940 KB Output is correct
35 Correct 304 ms 940 KB Output is correct
36 Correct 325 ms 1028 KB Output is correct
37 Correct 348 ms 684 KB Output is correct
38 Correct 325 ms 940 KB Output is correct
39 Correct 313 ms 1028 KB Output is correct
40 Correct 304 ms 780 KB Output is correct
41 Correct 279 ms 768 KB Output is correct
42 Correct 33 ms 768 KB Output is correct
43 Correct 61 ms 768 KB Output is correct
44 Correct 80 ms 716 KB Output is correct
45 Correct 97 ms 684 KB Output is correct
46 Correct 226 ms 684 KB Output is correct
47 Correct 201 ms 684 KB Output is correct
48 Correct 35 ms 848 KB Output is correct
49 Correct 28 ms 840 KB Output is correct