oj.uz

Submission #329690

# Submission time Handle Problem Language Result Execution time Memory
329690 2020-11-22T03:00:55 Z chenwz Stations (IOI20_stations) C++14
100 / 100
 1016 ms 1140 KB 
#include "stations.h"
#include <vector>

void rec(int index, int parent, int pre_order, int &number,
         std::vector<std::vector<int>>& con, std::vector<int>& labels) {
  if (pre_order) labels[index] = number++;
  for (int i : con[index]) {
    if (i == parent) continue;
    rec(i, index, !pre_order, number, con, labels);
  }
  if (!pre_order) labels[index] = number++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
  std::vector<int> labels(n);
  std::vector<std::vector<int>> con(n, std::vector<int>());
  for (int i = 0; i < u.size(); i++) {
    con[u[i]].push_back(v[i]);
    con[v[i]].push_back(u[i]);
  }
  int number = 0;
  rec(0, -1, true, number, con, labels);
  return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
  if (c[0] > s) {
    // Case 1: node s is in pre_order level.
    // All the neighbors are higher than s.

    if (t < s) {
      // The target is smaller than the source.
      // The target is definitely not in this subtree, go to parent.
      return c.back();
    }

    if (t > c.back()) {
      // The target is higher than the largest neighbor.
      // The target cannot be in this subtree, go to parent.
      return c.back();
    }

    // The target is in this subtree.
    // Pick the smallest child that's at least the target.
    int next = 0;
    while (c[next] < t) next++;
    return c[next];
  }


  // Case 2: node s is in the post_order level.
  if (t < c[0]) {
    // The target is smaller than the pre_order root c[0],
    // thus not in this subtree, go to the root.
    return c[0];
  }

  if (t > s) {
    // The target is higher than this post_order value.
    // Thus it's not in this subtree, go to the root.
    return c[0];
  }

  int next = c.size() - 1;
  while (c[next] > t) next--;
  return c[next];
}

Compilation message

stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:17:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for (int i = 0; i < u.size(); i++) {
      |                   ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 884 KB Output is correct
2 Correct 489 ms 1044 KB Output is correct
3 Correct 881 ms 920 KB Output is correct
4 Correct 636 ms 1140 KB Output is correct
5 Correct 657 ms 800 KB Output is correct
6 Correct 440 ms 884 KB Output is correct
7 Correct 493 ms 1128 KB Output is correct
8 Correct 2 ms 888 KB Output is correct
9 Correct 3 ms 736 KB Output is correct
10 Correct 0 ms 736 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 932 KB Output is correct
2 Correct 528 ms 800 KB Output is correct
3 Correct 909 ms 920 KB Output is correct
4 Correct 698 ms 860 KB Output is correct
5 Correct 643 ms 884 KB Output is correct
6 Correct 430 ms 756 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 972 KB Output is correct
2 Correct 432 ms 972 KB Output is correct
3 Correct 861 ms 888 KB Output is correct
4 Correct 654 ms 880 KB Output is correct
5 Correct 587 ms 752 KB Output is correct
6 Correct 423 ms 1104 KB Output is correct
7 Correct 532 ms 884 KB Output is correct
8 Correct 2 ms 928 KB Output is correct
9 Correct 5 ms 880 KB Output is correct
10 Correct 0 ms 736 KB Output is correct
11 Correct 763 ms 756 KB Output is correct
12 Correct 462 ms 928 KB Output is correct
13 Correct 493 ms 960 KB Output is correct
14 Correct 516 ms 808 KB Output is correct
15 Correct 62 ms 756 KB Output is correct
16 Correct 64 ms 736 KB Output is correct
17 Correct 96 ms 808 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1016 ms 864 KB Output is correct
2 Correct 626 ms 880 KB Output is correct
3 Correct 578 ms 888 KB Output is correct
4 Correct 2 ms 888 KB Output is correct
5 Correct 4 ms 880 KB Output is correct
6 Correct 0 ms 756 KB Output is correct
7 Correct 589 ms 736 KB Output is correct
8 Correct 841 ms 756 KB Output is correct
9 Correct 642 ms 880 KB Output is correct
10 Correct 635 ms 880 KB Output is correct
11 Correct 4 ms 888 KB Output is correct
12 Correct 4 ms 736 KB Output is correct
13 Correct 5 ms 928 KB Output is correct
14 Correct 3 ms 756 KB Output is correct
15 Correct 1 ms 756 KB Output is correct
16 Correct 494 ms 884 KB Output is correct
17 Correct 490 ms 880 KB Output is correct
18 Correct 496 ms 880 KB Output is correct
19 Correct 510 ms 880 KB Output is correct
20 Correct 489 ms 880 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 896 KB Output is correct
2 Correct 436 ms 864 KB Output is correct
3 Correct 840 ms 736 KB Output is correct
4 Correct 668 ms 880 KB Output is correct
5 Correct 566 ms 864 KB Output is correct
6 Correct 442 ms 864 KB Output is correct
7 Correct 424 ms 756 KB Output is correct
8 Correct 2 ms 888 KB Output is correct
9 Correct 4 ms 796 KB Output is correct
10 Correct 1 ms 736 KB Output is correct
11 Correct 445 ms 736 KB Output is correct
12 Correct 506 ms 940 KB Output is correct
13 Correct 857 ms 880 KB Output is correct
14 Correct 627 ms 1008 KB Output is correct
15 Correct 579 ms 804 KB Output is correct
16 Correct 428 ms 816 KB Output is correct
17 Correct 574 ms 880 KB Output is correct
18 Correct 442 ms 1128 KB Output is correct
19 Correct 473 ms 980 KB Output is correct
20 Correct 520 ms 736 KB Output is correct
21 Correct 51 ms 912 KB Output is correct
22 Correct 66 ms 736 KB Output is correct
23 Correct 102 ms 992 KB Output is correct
24 Correct 6 ms 736 KB Output is correct
25 Correct 6 ms 756 KB Output is correct
26 Correct 6 ms 880 KB Output is correct
27 Correct 4 ms 736 KB Output is correct
28 Correct 1 ms 736 KB Output is correct
29 Correct 524 ms 880 KB Output is correct
30 Correct 541 ms 756 KB Output is correct
31 Correct 548 ms 1008 KB Output is correct
32 Correct 619 ms 756 KB Output is correct
33 Correct 605 ms 756 KB Output is correct
34 Correct 384 ms 884 KB Output is correct
35 Correct 459 ms 1056 KB Output is correct
36 Correct 415 ms 984 KB Output is correct
37 Correct 503 ms 912 KB Output is correct
38 Correct 543 ms 936 KB Output is correct
39 Correct 442 ms 992 KB Output is correct
40 Correct 469 ms 868 KB Output is correct
41 Correct 523 ms 864 KB Output is correct
42 Correct 64 ms 820 KB Output is correct
43 Correct 127 ms 884 KB Output is correct
44 Correct 123 ms 1012 KB Output is correct
45 Correct 210 ms 1032 KB Output is correct
46 Correct 346 ms 812 KB Output is correct
47 Correct 299 ms 764 KB Output is correct
48 Correct 65 ms 796 KB Output is correct
49 Correct 62 ms 936 KB Output is correct