oj.uz

Submission #443129

# Submission time Handle Problem Language Result Execution time Memory
443129 2021-07-09T18:41:37 Z peijar Stations (IOI20_stations) C++17
100 / 100
 1117 ms 776 KB 
#include "stations.h"
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
using namespace std;

vector<vector<int>> adj;
vector<int> tin, tout;
vector<int> depth;
int curTime;

void dfs(int u, int p) {
  tin[u] = curTime++;
  for (int v : adj[u])
    if (v != p) {
      depth[v] = depth[u] + 1;
      dfs(v, u);
    }
  tout[u] = curTime++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
  curTime = 0;
  tin.clear();
  tout.clear();
  depth.clear();
  adj.clear();
  tin.resize(n), tout.resize(n), adj.resize(n), depth.resize(n);
  for (int i = 0; i < n - 1; ++i) {
    adj[u[i]].push_back(v[i]);
    adj[v[i]].push_back(u[i]);
  }
  dfs(0, 0);
  vector<int> labels(n);
  for (int i = 0; i < n; i++)
    labels[i] = depth[i] % 2 ? tout[i] : tin[i];
  vector<int> dis;
  for (auto l : labels)
    dis.push_back(l);
  sort(dis.begin(), dis.end());
  dis.resize(unique(dis.begin(), dis.end()) - dis.begin());
  for (int &i : labels)
    i = lower_bound(dis.begin(), dis.end(), i) - dis.begin();

  // for (int x : labels)
  // cerr << x << ' ';
  // cerr << endl;
  return labels;
}

int find_next_station(int s, int t, vector<int> c) {
  if (!s) {
    for (int i = 0; i < (int)c.size(); ++i)
      if (t <= c[i])
        return c[i];
  }
  if (c.size() == 1)
    return c[0];
  for (auto v : c)
    if (v == t)
      return v;

  bool allGreater = true, allLess = true;
  for (int i : c)
    allGreater &= i > s, allLess &= i < s;

  if (allGreater) { // s is tin, all others are tout
    int p = c.back();
    c.pop_back();
    if (t < c[0] and t > s)
      return c[0];
    for (int i = 1; i < (int)c.size(); ++i)
      if (t < c[i] and t > c[i - 1])
        return c[i];
    return p;
  } else { // s is tout and all others are tin
    int p = c.front();
    c.erase(c.begin());
    if (t > c.back() and t < s)
      return c.back();
    for (int i = 0; i + 1 < (int)c.size(); ++i)
      if (t > c[i] and t < c[i + 1])
        return c[i];
    return p;
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 736 KB Output is correct
2 Correct 613 ms 528 KB Output is correct
3 Correct 853 ms 500 KB Output is correct
4 Correct 802 ms 488 KB Output is correct
5 Correct 692 ms 488 KB Output is correct
6 Correct 528 ms 528 KB Output is correct
7 Correct 457 ms 528 KB Output is correct
8 Correct 4 ms 476 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 0 ms 464 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 620 KB Output is correct
2 Correct 668 ms 484 KB Output is correct
3 Correct 1027 ms 400 KB Output is correct
4 Correct 746 ms 488 KB Output is correct
5 Correct 679 ms 400 KB Output is correct
6 Correct 525 ms 656 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 656 KB Output is correct
2 Correct 506 ms 636 KB Output is correct
3 Correct 991 ms 512 KB Output is correct
4 Correct 842 ms 488 KB Output is correct
5 Correct 657 ms 400 KB Output is correct
6 Correct 432 ms 616 KB Output is correct
7 Correct 513 ms 520 KB Output is correct
8 Correct 3 ms 472 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 739 ms 472 KB Output is correct
12 Correct 497 ms 712 KB Output is correct
13 Correct 593 ms 604 KB Output is correct
14 Correct 565 ms 528 KB Output is correct
15 Correct 44 ms 468 KB Output is correct
16 Correct 74 ms 492 KB Output is correct
17 Correct 110 ms 584 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1004 ms 400 KB Output is correct
2 Correct 698 ms 488 KB Output is correct
3 Correct 606 ms 400 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 758 ms 484 KB Output is correct
8 Correct 1001 ms 464 KB Output is correct
9 Correct 753 ms 592 KB Output is correct
10 Correct 734 ms 492 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Correct 8 ms 468 KB Output is correct
13 Correct 4 ms 468 KB Output is correct
14 Correct 4 ms 476 KB Output is correct
15 Correct 0 ms 468 KB Output is correct
16 Correct 645 ms 400 KB Output is correct
17 Correct 558 ms 488 KB Output is correct
18 Correct 543 ms 400 KB Output is correct
19 Correct 636 ms 400 KB Output is correct
20 Correct 531 ms 488 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 732 KB Output is correct
2 Correct 583 ms 608 KB Output is correct
3 Correct 1117 ms 492 KB Output is correct
4 Correct 766 ms 428 KB Output is correct
5 Correct 609 ms 400 KB Output is correct
6 Correct 523 ms 644 KB Output is correct
7 Correct 550 ms 520 KB Output is correct
8 Correct 3 ms 476 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 492 ms 584 KB Output is correct
12 Correct 669 ms 500 KB Output is correct
13 Correct 1001 ms 400 KB Output is correct
14 Correct 724 ms 428 KB Output is correct
15 Correct 644 ms 400 KB Output is correct
16 Correct 546 ms 528 KB Output is correct
17 Correct 686 ms 492 KB Output is correct
18 Correct 536 ms 532 KB Output is correct
19 Correct 558 ms 688 KB Output is correct
20 Correct 438 ms 528 KB Output is correct
21 Correct 60 ms 420 KB Output is correct
22 Correct 66 ms 548 KB Output is correct
23 Correct 97 ms 488 KB Output is correct
24 Correct 6 ms 468 KB Output is correct
25 Correct 5 ms 468 KB Output is correct
26 Correct 6 ms 476 KB Output is correct
27 Correct 3 ms 468 KB Output is correct
28 Correct 1 ms 476 KB Output is correct
29 Correct 545 ms 488 KB Output is correct
30 Correct 589 ms 400 KB Output is correct
31 Correct 482 ms 488 KB Output is correct
32 Correct 471 ms 492 KB Output is correct
33 Correct 543 ms 400 KB Output is correct
34 Correct 333 ms 656 KB Output is correct
35 Correct 520 ms 528 KB Output is correct
36 Correct 465 ms 736 KB Output is correct
37 Correct 543 ms 528 KB Output is correct
38 Correct 584 ms 700 KB Output is correct
39 Correct 606 ms 600 KB Output is correct
40 Correct 453 ms 684 KB Output is correct
41 Correct 566 ms 616 KB Output is correct
42 Correct 77 ms 548 KB Output is correct
43 Correct 147 ms 488 KB Output is correct
44 Correct 171 ms 776 KB Output is correct
45 Correct 155 ms 528 KB Output is correct
46 Correct 340 ms 528 KB Output is correct
47 Correct 385 ms 528 KB Output is correct
48 Correct 76 ms 528 KB Output is correct
49 Correct 55 ms 604 KB Output is correct