oj.uz

Submission #390840

# Submission time Handle Problem Language Result Execution time Memory
390840 2021-04-17T07:06:28 Z AlexPop28 Stations (IOI20_stations) C++14
100 / 100
 1172 ms 736 KB 
#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

void DFS(int node, int par, int depth, int &timer, 
  vector<int> &ans, const vector<vector<int>> &adj) {
  
  if (depth == 0) ans[node] = timer++;
  for (auto &x : adj[node]) {
    if (x == par) continue;
    DFS(x, node, 1 - depth, timer, ans, adj);
  }
  if (depth == 1) ans[node] = timer++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> ans(n);
  vector<vector<int>> adj(n); 
  for (int i = 0; i < n - 1; ++i) {
    adj[u[i]].emplace_back(v[i]);
    adj[v[i]].emplace_back(u[i]);
  }

  int timer = 0;
  DFS(0, -1, 0, timer, ans, adj);
  return ans;
}

int find_next_station(int s, int t, vector<int> c) {
  if ((int)c.size() == 1) { 
    return c[0];
  }

  if (s < c[0]) { // sunt nod de in-time 
    // c.back() e par
    if (s < t && t <= c[0]) {
      return c[0];
    }
    for (int i = 0; i + 1 < (int)c.size() - 1; ++i) {
      if (c[i] < t && t <= c[i + 1]) return c[i + 1]; 
    }
    return c.back();
  } else { // sunt nod de out-time
    assert(s > c.back());
    // c[0] e par
    if (c.back() <= t && t < s) {
      return c.back();
    }
    for (int i = 1; i + 1 < (int)c.size(); ++i) {
      if (c[i] <= t && t < c[i + 1]) return c[i];
    }
    return c[0];
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 528 KB Output is correct
2 Correct 584 ms 560 KB Output is correct
3 Correct 1049 ms 400 KB Output is correct
4 Correct 850 ms 496 KB Output is correct
5 Correct 648 ms 492 KB Output is correct
6 Correct 542 ms 624 KB Output is correct
7 Correct 494 ms 532 KB Output is correct
8 Correct 3 ms 472 KB Output is correct
9 Correct 6 ms 460 KB Output is correct
10 Correct 2 ms 472 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 528 KB Output is correct
2 Correct 600 ms 480 KB Output is correct
3 Correct 1031 ms 548 KB Output is correct
4 Correct 771 ms 400 KB Output is correct
5 Correct 641 ms 492 KB Output is correct
6 Correct 443 ms 488 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 528 KB Output is correct
2 Correct 568 ms 656 KB Output is correct
3 Correct 1146 ms 620 KB Output is correct
4 Correct 752 ms 488 KB Output is correct
5 Correct 765 ms 492 KB Output is correct
6 Correct 573 ms 528 KB Output is correct
7 Correct 433 ms 520 KB Output is correct
8 Correct 3 ms 472 KB Output is correct
9 Correct 5 ms 472 KB Output is correct
10 Correct 2 ms 472 KB Output is correct
11 Correct 685 ms 492 KB Output is correct
12 Correct 522 ms 608 KB Output is correct
13 Correct 578 ms 712 KB Output is correct
14 Correct 598 ms 556 KB Output is correct
15 Correct 53 ms 472 KB Output is correct
16 Correct 87 ms 656 KB Output is correct
17 Correct 101 ms 552 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1172 ms 488 KB Output is correct
2 Correct 697 ms 408 KB Output is correct
3 Correct 662 ms 400 KB Output is correct
4 Correct 3 ms 480 KB Output is correct
5 Correct 4 ms 480 KB Output is correct
6 Correct 2 ms 480 KB Output is correct
7 Correct 755 ms 400 KB Output is correct
8 Correct 1000 ms 404 KB Output is correct
9 Correct 843 ms 400 KB Output is correct
10 Correct 583 ms 480 KB Output is correct
11 Correct 7 ms 480 KB Output is correct
12 Correct 7 ms 484 KB Output is correct
13 Correct 4 ms 484 KB Output is correct
14 Correct 5 ms 480 KB Output is correct
15 Correct 2 ms 472 KB Output is correct
16 Correct 520 ms 428 KB Output is correct
17 Correct 578 ms 400 KB Output is correct
18 Correct 647 ms 400 KB Output is correct
19 Correct 679 ms 400 KB Output is correct
20 Correct 635 ms 404 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 616 KB Output is correct
2 Correct 599 ms 624 KB Output is correct
3 Correct 1123 ms 472 KB Output is correct
4 Correct 758 ms 492 KB Output is correct
5 Correct 757 ms 488 KB Output is correct
6 Correct 539 ms 528 KB Output is correct
7 Correct 584 ms 656 KB Output is correct
8 Correct 3 ms 472 KB Output is correct
9 Correct 7 ms 480 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 528 ms 484 KB Output is correct
12 Correct 724 ms 492 KB Output is correct
13 Correct 1101 ms 520 KB Output is correct
14 Correct 741 ms 528 KB Output is correct
15 Correct 801 ms 616 KB Output is correct
16 Correct 604 ms 552 KB Output is correct
17 Correct 700 ms 520 KB Output is correct
18 Correct 512 ms 648 KB Output is correct
19 Correct 558 ms 736 KB Output is correct
20 Correct 442 ms 528 KB Output is correct
21 Correct 72 ms 472 KB Output is correct
22 Correct 91 ms 552 KB Output is correct
23 Correct 128 ms 528 KB Output is correct
24 Correct 4 ms 472 KB Output is correct
25 Correct 8 ms 472 KB Output is correct
26 Correct 6 ms 472 KB Output is correct
27 Correct 4 ms 480 KB Output is correct
28 Correct 2 ms 472 KB Output is correct
29 Correct 532 ms 400 KB Output is correct
30 Correct 556 ms 488 KB Output is correct
31 Correct 659 ms 496 KB Output is correct
32 Correct 572 ms 488 KB Output is correct
33 Correct 585 ms 400 KB Output is correct
34 Correct 327 ms 544 KB Output is correct
35 Correct 418 ms 624 KB Output is correct
36 Correct 446 ms 700 KB Output is correct
37 Correct 467 ms 612 KB Output is correct
38 Correct 500 ms 492 KB Output is correct
39 Correct 580 ms 616 KB Output is correct
40 Correct 502 ms 580 KB Output is correct
41 Correct 426 ms 692 KB Output is correct
42 Correct 79 ms 656 KB Output is correct
43 Correct 145 ms 556 KB Output is correct
44 Correct 131 ms 496 KB Output is correct
45 Correct 221 ms 528 KB Output is correct
46 Correct 283 ms 532 KB Output is correct
47 Correct 322 ms 532 KB Output is correct
48 Correct 78 ms 660 KB Output is correct
49 Correct 72 ms 640 KB Output is correct