oj.uz

Submission #559055

# Submission time Handle Problem Language Result Execution time Memory
559055 2022-05-09T10:19:26 Z Mamedov Stations (IOI20_stations) C++17
100 / 100
 782 ms 840 KB 
#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

/*
  Label v with tin[v] for even levels and tout[v] for odd levels.
  This gives us labels of even numbers between [0, 2*n-2].
  We can divide each label by 2, so we get all labels in [0, n-1]

  Note: We can always restore [tin[v], tout[v]] by v and its neighbors' labels.
*/

void dfs(int v, int par, int level, int &timer, vector<int> &tin, vector<int> &tout, vector<int> &labels, vector<vector<int>> &g) {
  tin[v] = timer++;
  for (int to : g[v]) {
    if (to != par) {
      dfs(to, v, level + 1, timer, tin, tout, labels, g);
    }
  }
  tout[v] = timer++;
  if (level % 2 == 0) {
    labels[v] = tin[v] / 2;
  } else {
    labels[v] = tout[v] / 2;
  }
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
  vector<vector<int>>g(n);
  vector<int>tin(n), tout(n);
  vector<int>labels(n);
  int timer = 0;
  for (int i = 0; i < n - 1; ++i) {
    g[u[i]].emplace_back(v[i]);
    g[v[i]].emplace_back(u[i]);
  }
  dfs(0, 0, 0, timer, tin, tout, labels, g);
  return labels;
}

int find_next_station(int s, int t, vector<int> c) {
  if (c[0] > s) {  /// s is labeled with tin[]
    if (t < s) {
      return c.back();
    } else {
      auto itr = lower_bound(c.begin(), c.end(), t);
      if (itr == c.end()) --itr;
      return (*itr);
    }
  } else {  /// s is labeled with tout[]
    if (t > s) {
      return c[0];
    } else {
      auto itr = upper_bound(c.begin(), c.end(), t);
      if (itr != c.begin()) --itr;
      return (*itr);
    }
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 672 KB Output is correct
2 Correct 364 ms 624 KB Output is correct
3 Correct 774 ms 488 KB Output is correct
4 Correct 488 ms 508 KB Output is correct
5 Correct 557 ms 500 KB Output is correct
6 Correct 391 ms 632 KB Output is correct
7 Correct 408 ms 668 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 4 ms 500 KB Output is correct
10 Correct 0 ms 492 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 512 KB Output is correct
2 Correct 462 ms 544 KB Output is correct
3 Correct 762 ms 416 KB Output is correct
4 Correct 557 ms 420 KB Output is correct
5 Correct 431 ms 504 KB Output is correct
6 Correct 376 ms 512 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 672 KB Output is correct
2 Correct 343 ms 632 KB Output is correct
3 Correct 744 ms 420 KB Output is correct
4 Correct 523 ms 420 KB Output is correct
5 Correct 522 ms 420 KB Output is correct
6 Correct 405 ms 676 KB Output is correct
7 Correct 387 ms 640 KB Output is correct
8 Correct 2 ms 500 KB Output is correct
9 Correct 5 ms 492 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 508 ms 504 KB Output is correct
12 Correct 393 ms 764 KB Output is correct
13 Correct 403 ms 756 KB Output is correct
14 Correct 392 ms 568 KB Output is correct
15 Correct 47 ms 492 KB Output is correct
16 Correct 65 ms 572 KB Output is correct
17 Correct 82 ms 596 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 768 ms 464 KB Output is correct
2 Correct 597 ms 416 KB Output is correct
3 Correct 551 ms 420 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 471 ms 500 KB Output is correct
8 Correct 749 ms 508 KB Output is correct
9 Correct 577 ms 416 KB Output is correct
10 Correct 486 ms 416 KB Output is correct
11 Correct 4 ms 492 KB Output is correct
12 Correct 5 ms 492 KB Output is correct
13 Correct 4 ms 496 KB Output is correct
14 Correct 3 ms 476 KB Output is correct
15 Correct 3 ms 492 KB Output is correct
16 Correct 417 ms 416 KB Output is correct
17 Correct 449 ms 416 KB Output is correct
18 Correct 480 ms 504 KB Output is correct
19 Correct 425 ms 500 KB Output is correct
20 Correct 448 ms 420 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 493 ms 672 KB Output is correct
2 Correct 394 ms 636 KB Output is correct
3 Correct 749 ms 416 KB Output is correct
4 Correct 593 ms 508 KB Output is correct
5 Correct 517 ms 420 KB Output is correct
6 Correct 348 ms 676 KB Output is correct
7 Correct 381 ms 548 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 1 ms 488 KB Output is correct
11 Correct 419 ms 548 KB Output is correct
12 Correct 453 ms 548 KB Output is correct
13 Correct 782 ms 416 KB Output is correct
14 Correct 568 ms 420 KB Output is correct
15 Correct 446 ms 504 KB Output is correct
16 Correct 427 ms 548 KB Output is correct
17 Correct 498 ms 504 KB Output is correct
18 Correct 399 ms 744 KB Output is correct
19 Correct 435 ms 756 KB Output is correct
20 Correct 441 ms 548 KB Output is correct
21 Correct 61 ms 444 KB Output is correct
22 Correct 65 ms 596 KB Output is correct
23 Correct 91 ms 548 KB Output is correct
24 Correct 6 ms 500 KB Output is correct
25 Correct 5 ms 500 KB Output is correct
26 Correct 4 ms 504 KB Output is correct
27 Correct 3 ms 492 KB Output is correct
28 Correct 2 ms 500 KB Output is correct
29 Correct 435 ms 500 KB Output is correct
30 Correct 437 ms 508 KB Output is correct
31 Correct 370 ms 504 KB Output is correct
32 Correct 375 ms 420 KB Output is correct
33 Correct 446 ms 516 KB Output is correct
34 Correct 258 ms 544 KB Output is correct
35 Correct 427 ms 840 KB Output is correct
36 Correct 396 ms 704 KB Output is correct
37 Correct 432 ms 548 KB Output is correct
38 Correct 397 ms 672 KB Output is correct
39 Correct 375 ms 820 KB Output is correct
40 Correct 417 ms 616 KB Output is correct
41 Correct 422 ms 716 KB Output is correct
42 Correct 60 ms 548 KB Output is correct
43 Correct 109 ms 544 KB Output is correct
44 Correct 112 ms 548 KB Output is correct
45 Correct 144 ms 676 KB Output is correct
46 Correct 267 ms 548 KB Output is correct
47 Correct 254 ms 548 KB Output is correct
48 Correct 61 ms 732 KB Output is correct
49 Correct 56 ms 732 KB Output is correct