oj.uz

Submission #306064

# Submission time Handle Problem Language Result Execution time Memory
306064 2020-09-24T12:23:57 Z eriksuenderhauf Stations (IOI20_stations) C++17
10 / 100
 966 ms 752 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);
  // if (*max_element(deg.begin(), deg.end()) <= 2) {
  //   int r = min_element(deg.begin(), deg.end()) - deg.begin(), p = -1;
  //   labels[r] = 0;
  //   for (int i = 1; i < n; i++) {
  //     if (~p) adj[r].erase(find(adj[r].begin(), adj[r].end(), p));
  //     tie(r, p) = make_pair(adj[r][0], r);
  //     labels[r] = i;
  //   }

  // iota(labels.begin(), labels.end(), 0);

  // function<void(int,int,int)> dfs = [&](int u, int p, int l) {
  //   labels[u] = l;
  //   adj[u].erase(find(adj[u].begin(), adj[u].end(), p));
  //   if (!adj[u].empty())
  //     dfs(adj[u][0], u, l+1);
  // };
  // int r = max_element(deg.begin(), deg.end()) - deg.begin();
  // int lo = 1; labels[r] = 0;
  // for (int v: adj[r]) {
  //   dfs(v, r, lo);
  //   lo += 1000;
  // }

  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 = [&](int u, int& l) {
    l |= 1 << u;
    for (int v: adj[u])
      dfs(v, l);
  };
  for (int i = 0; i < n; i++) {
    dfs(i, labels[i]);
    labels[i] |= i << 8;
  }
  return labels;
}

int find_next_station(int s, int t, vector<int> c) {
  vector<int> cand;
  int y = t >> 8, x = s >> 8;
  for (int i: c)
    if ((i >> y) & 1)
      cand.push_back(i);
  if (cand.size() == 1) return cand[0];
  if (cand.size() == 2) {
    int lo = cand[0] >> 8, hi = cand[1] >> 8;
    if ((cand[0] >> hi) & 1)
      return cand[1];
    return cand[0];
  }
  for (int i: c)
    if ((i >> x) & 1)
      return i;
  assert(0);

  // sort(c.begin(), c.end());
  // if (t == 0)
  //   return c[0];
  // if (s == 0)
  //   return ((t-1) / 1000) * 1000 + 1;
  // if ((s-1) / 1000 == (t-1) / 1000)
  //   return s < t ? c.back() : c[0];
  // return c[0];

  // 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());

  // return s < t ? *max_element(c.begin(), c.end()) : *min_element(c.begin(), c.end());
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:61:9: warning: unused variable 'lo' [-Wunused-variable]
   61 |     int lo = cand[0] >> 8, hi = cand[1] >> 8;
      |         ^~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 927 ms 640 KB Output is correct
2 Correct 706 ms 640 KB Output is correct
3 Correct 599 ms 640 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 2 ms 652 KB Output is correct
7 Correct 644 ms 640 KB Output is correct
8 Correct 966 ms 752 KB Output is correct
9 Correct 725 ms 640 KB Output is correct
10 Correct 662 ms 644 KB Output is correct
11 Correct 6 ms 656 KB Output is correct
12 Correct 5 ms 648 KB Output is correct
13 Correct 5 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 534 ms 640 KB Output is correct
17 Correct 571 ms 656 KB Output is correct
18 Correct 625 ms 640 KB Output is correct
19 Correct 724 ms 644 KB Output is correct
20 Correct 742 ms 640 KB Output is correct

Subtask #5
0 / 61.0

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