oj.uz

Submission #306075

# Submission time Handle Problem Language Result Execution time Memory
306075 2020-09-24T12:37:38 Z eriksuenderhauf Stations (IOI20_stations) C++17
10 / 100
 984 ms 776 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<int> deg(n);
  vector<vector<int>> adj(n);
  for (int i = 0; i < n - 1; i++)
    deg[u[i]]++, deg[v[i]]++, adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]);;
  vector<int> labels(n);
  function<void(int,int)> init = [&](int u, int p) {
    if (~p) adj[u].erase(find(adj[u].begin(), adj[u].end(), p));
    for (int v: adj[u])
      init(v, u);
  };
  init(0, -1);
  function<void(int,int)> dfs;
  function<void(int,int,int,int)> join = [&](int u, int l, int r, int v) {
    if (l > r) return;
    if (l == r)
      dfs(adj[u][l], 2*v+1);
    else {
      int m = (l+r) / 2;
      join(u, l, m, v*2+1);
      join(u, m+1, r, v*2+2);
    }
  };
  dfs = [&](int u, int l) {
    labels[u] = l;
    join(u, 0, adj[u].size()-1, l);
  };
  dfs(0, 0);
  return labels;
}

int find_next_station(int s, int t, vector<int> c) {
  set<int> tmp; for (int x: c) tmp.insert(x+1);
  int y = t+1;
  if (tmp.count(y)) return y-1;
  while (y > 0) {
    y /= 2;
    if (tmp.count(y))
      return y-1;
  }
  return *min_element(c.begin(), c.end());
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 877 ms 640 KB Output is correct
2 Correct 688 ms 776 KB Output is correct
3 Correct 645 ms 644 KB Output is correct
4 Correct 3 ms 644 KB Output is correct
5 Correct 4 ms 648 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 682 ms 640 KB Output is correct
8 Correct 984 ms 640 KB Output is correct
9 Correct 694 ms 640 KB Output is correct
10 Correct 570 ms 640 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 6 ms 652 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Correct 4 ms 640 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 485 ms 644 KB Output is correct
17 Correct 503 ms 648 KB Output is correct
18 Correct 524 ms 644 KB Output is correct
19 Correct 664 ms 640 KB Output is correct
20 Correct 532 ms 640 KB Output is correct

Subtask #5
0 / 61.0

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