oj.uz

Submission #640968

# Submission time Handle Problem Language Result Execution time Memory
640968 2022-09-15T15:31:25 Z t6twotwo Stations (IOI20_stations) C++17
100 / 100
 886 ms 876 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
  vector<vector<int>> adj(n);
  for (int i = 0; i < n - 1; i++) {
    adj[u[i]].push_back(v[i]);
    adj[v[i]].push_back(u[i]);
  }
  int cnt = 0;
  vector<int> ans(n);
  function<void(int, int, int)> dfs = [&](int a, int c, int d) {
    if (d == 0) {
      ans[a] = cnt++;
    }
    for (int b : adj[a]) {
      if (b != c) {
        dfs(b, a, d ^ 1);
      }
    }
    if (d == 1) {
      ans[a] = cnt++;
    }
  };
  dfs(0, -1, 0);
  return ans;
}
int find_next_station(int s, int t, vector<int> c) {
  if (s < c[0]) {
    if (t < s || t >= c.back()) {
      return c.back();
    }
    return *lower_bound(c.begin(), c.end(), t);
  } else {
    if (t > s || t < c[0]) {
      return c[0];
    }
    return *--upper_bound(c.begin(), c.end(), t);
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 632 KB Output is correct
2 Correct 463 ms 632 KB Output is correct
3 Correct 850 ms 508 KB Output is correct
4 Correct 638 ms 416 KB Output is correct
5 Correct 565 ms 500 KB Output is correct
6 Correct 427 ms 704 KB Output is correct
7 Correct 374 ms 632 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 4 ms 500 KB Output is correct
10 Correct 0 ms 500 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 504 KB Output is correct
2 Correct 513 ms 572 KB Output is correct
3 Correct 775 ms 508 KB Output is correct
4 Correct 634 ms 504 KB Output is correct
5 Correct 544 ms 504 KB Output is correct
6 Correct 405 ms 512 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 676 KB Output is correct
2 Correct 472 ms 632 KB Output is correct
3 Correct 837 ms 504 KB Output is correct
4 Correct 676 ms 508 KB Output is correct
5 Correct 570 ms 416 KB Output is correct
6 Correct 415 ms 632 KB Output is correct
7 Correct 451 ms 544 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 2 ms 500 KB Output is correct
10 Correct 2 ms 496 KB Output is correct
11 Correct 579 ms 532 KB Output is correct
12 Correct 455 ms 876 KB Output is correct
13 Correct 453 ms 676 KB Output is correct
14 Correct 445 ms 504 KB Output is correct
15 Correct 57 ms 492 KB Output is correct
16 Correct 68 ms 556 KB Output is correct
17 Correct 109 ms 548 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 886 ms 416 KB Output is correct
2 Correct 553 ms 500 KB Output is correct
3 Correct 608 ms 568 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 507 ms 416 KB Output is correct
8 Correct 766 ms 416 KB Output is correct
9 Correct 615 ms 504 KB Output is correct
10 Correct 569 ms 508 KB Output is correct
11 Correct 5 ms 492 KB Output is correct
12 Correct 4 ms 500 KB Output is correct
13 Correct 6 ms 500 KB Output is correct
14 Correct 3 ms 500 KB Output is correct
15 Correct 1 ms 500 KB Output is correct
16 Correct 485 ms 420 KB Output is correct
17 Correct 430 ms 500 KB Output is correct
18 Correct 487 ms 416 KB Output is correct
19 Correct 506 ms 508 KB Output is correct
20 Correct 470 ms 420 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 648 KB Output is correct
2 Correct 364 ms 656 KB Output is correct
3 Correct 820 ms 420 KB Output is correct
4 Correct 528 ms 420 KB Output is correct
5 Correct 534 ms 508 KB Output is correct
6 Correct 479 ms 672 KB Output is correct
7 Correct 343 ms 628 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 451 ms 500 KB Output is correct
12 Correct 577 ms 548 KB Output is correct
13 Correct 797 ms 516 KB Output is correct
14 Correct 575 ms 504 KB Output is correct
15 Correct 509 ms 416 KB Output is correct
16 Correct 439 ms 512 KB Output is correct
17 Correct 589 ms 416 KB Output is correct
18 Correct 450 ms 716 KB Output is correct
19 Correct 524 ms 700 KB Output is correct
20 Correct 413 ms 492 KB Output is correct
21 Correct 50 ms 420 KB Output is correct
22 Correct 93 ms 504 KB Output is correct
23 Correct 90 ms 504 KB Output is correct
24 Correct 7 ms 492 KB Output is correct
25 Correct 6 ms 492 KB Output is correct
26 Correct 4 ms 488 KB Output is correct
27 Correct 4 ms 500 KB Output is correct
28 Correct 2 ms 512 KB Output is correct
29 Correct 493 ms 504 KB Output is correct
30 Correct 602 ms 416 KB Output is correct
31 Correct 579 ms 416 KB Output is correct
32 Correct 521 ms 500 KB Output is correct
33 Correct 506 ms 508 KB Output is correct
34 Correct 499 ms 632 KB Output is correct
35 Correct 472 ms 632 KB Output is correct
36 Correct 474 ms 756 KB Output is correct
37 Correct 451 ms 620 KB Output is correct
38 Correct 521 ms 584 KB Output is correct
39 Correct 499 ms 716 KB Output is correct
40 Correct 478 ms 632 KB Output is correct
41 Correct 505 ms 640 KB Output is correct
42 Correct 72 ms 568 KB Output is correct
43 Correct 174 ms 588 KB Output is correct
44 Correct 131 ms 544 KB Output is correct
45 Correct 157 ms 548 KB Output is correct
46 Correct 263 ms 544 KB Output is correct
47 Correct 328 ms 544 KB Output is correct
48 Correct 41 ms 668 KB Output is correct
49 Correct 50 ms 672 KB Output is correct