oj.uz

Submission #443122

# Submission time Handle Problem Language Result Execution time Memory
443122 2021-07-09T18:31:07 Z peijar Stations (IOI20_stations) C++17
0 / 100
 1059 ms 780 KB 
#include "stations.h"
#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.resize(n), tout.resize(n), adj.clear(), depth.resize(n);
  adj.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];

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

int find_next_station(int s, int t, vector<int> c) {
  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 t;
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 416 KB Invalid labels (values out of range). scenario=2, k=1000, vertex=1, label=1990
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 380 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1022
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 615 ms 652 KB Output is correct
2 Correct 513 ms 636 KB Output is correct
3 Correct 1059 ms 404 KB Output is correct
4 Correct 900 ms 400 KB Output is correct
5 Correct 657 ms 400 KB Output is correct
6 Correct 509 ms 660 KB Output is correct
7 Correct 484 ms 616 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 623 ms 480 KB Output is correct
12 Incorrect 575 ms 780 KB Wrong query response.
13 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 934 ms 520 KB Output is correct
2 Correct 754 ms 520 KB Output is correct
3 Correct 644 ms 484 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 5 ms 472 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 747 ms 400 KB Output is correct
8 Correct 1008 ms 520 KB Output is correct
9 Correct 732 ms 484 KB Output is correct
10 Correct 600 ms 400 KB Output is correct
11 Incorrect 7 ms 468 KB Wrong query response.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 671 ms 616 KB Partially correct
2 Partially correct 625 ms 648 KB Partially correct
3 Correct 952 ms 400 KB Output is correct
4 Correct 874 ms 528 KB Output is correct
5 Correct 673 ms 400 KB Output is correct
6 Partially correct 554 ms 708 KB Partially correct
7 Partially correct 513 ms 616 KB Partially correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Incorrect 585 ms 620 KB Wrong query response.
12 Halted 0 ms 0 KB -