oj.uz

Submission #835263

# Submission time Handle Problem Language Result Execution time Memory
835263 2023-08-23T11:19:34 Z Johann Werewolf (IOI18_werewolf) C++14
0 / 100
 514 ms 192944 KB 
#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N, Q, M;
vi S, E, L, R;
vvi adj;
vvi Eadj, Sadj;
vi Ein, Eout, Sin, Sout;
vvi Elift, Slift;
vi depth;
int idx;

struct unionfind
{
  vi arr;
  void init(int size)
  {
    arr.resize(size);
    iota(all(arr), 0);
  }
  int find(int i) { return arr[i] = (arr[i] == i) ? i : find(arr[i]); }
  void combine(int a, int b)
  {
    // a is the one it gets merged to
    a = find(a), b = find(b);
    arr[b] = a;
  }
};
unionfind uf;

void dfs(vvi &A, int v, int p, vi &in, vi &out, vvi &lift)
{
  in[v] = idx++;
  lift[v][0] = p;
  for (int j = 1; j < sz(lift[v]); ++j)
    lift[v][j] = lift[lift[v][j - 1]][j - 1];
  for (int u : A[v])
    if (u != p)
      dfs(A, u, v, in, out, lift);
  out[v] = idx++;
}
bool is_vorg(int a, int b, vi &in, vi &out)
{
  return in[a] <= in[b] && out[b] <= out[a];
}

vvpii tocheck;          // [e] := list of s values with whom the subtree comparison should work
vector<set<int>> nodes; // [e] := set of all invalues my nodes have in S
vi A;                   // the answer
void answer(int v, int p)
{
  // going through e per definition
  nodes[v].insert(Sin[v]);
  for (int u : Eadj[v])
    if (u != p)
    {
      answer(u, v);
      if (sz(nodes[u]) > sz(nodes[v]))
        swap(u, v);
      for (int x : nodes[u])
        nodes[v].insert(x);
    }

  for (pii tmp : tocheck[v])
  {
    int s, q;
    tie(s, q) = tmp;
    A[q] = (*nodes[v].lower_bound(Sin[s]) < Sout[s]);
  }
}

std::vector<int> check_validity(int _N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> _S, std::vector<int> _E,
                                std::vector<int> _L, std::vector<int> _R)
{
  N = _N, Q = sz(_S), M = sz(X);
  S = _S, E = _E, L = _L, R = _R;

  adj.assign(N, vi());
  for (int i = 0; i < M; ++i)
    adj[X[i]].push_back(Y[i]), adj[Y[i]].push_back(X[i]);

  Eadj.assign(N, vi());
  uf.init(N);
  for (int v = 0; v < N; ++v)
  {
    for (int u : adj[v])
      if (u < v)
      {
        u = uf.find(u);
        if (u != v)
          Eadj[v].push_back(u), uf.combine(v, u);
      }
  }
  idx = 0;
  Ein.resize(N), Eout.resize(N);
  Elift.assign(N, vi(ceil(log2(N))));
  dfs(Eadj, N - 1, N - 1, Ein, Eout, Elift);

  Sadj.assign(N, vi());
  uf.init(N);
  for (int v = N - 1; v >= 0; --v)
  {
    for (int u : adj[v])
      if (u > v)
      {
        u = uf.find(u);
        if (u != v)
          Sadj[v].push_back(u), uf.combine(v, u);
      }
  }
  idx = 0;
  Sin.resize(N), Sout.resize(N);
  Slift.assign(N, vi(ceil(log2(N))));
  dfs(Sadj, 0, 0, Sin, Sout, Slift);

  tocheck.assign(N, vpii());
  for (int q = 0; q < Q; ++q)
  {
    int Enode = E[q];
    for (int j = sz(Elift[Enode]) - 1; j >= 0; --j)
      if (Elift[Enode][j] <= R[q])
        Enode = Elift[Enode][j];

    int Snode = S[q];
    for (int j = sz(Slift[Snode]) - 1; j >= 0; --j)
      if (Slift[Snode][j] >= L[q])
        Snode = Slift[Snode][j];

    tocheck[Enode].push_back({Snode, q});
  }

  A.assign(Q, 0);
  answer(N - 1, N - 1);

  return A;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 514 ms 192944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -