oj.uz

Submission #835251

# Submission time Handle Problem Language Result Execution time Memory
835251 2023-08-23T11:10:52 Z Johann Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 102220 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;
#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];
}

bool answer(int e, int s)
{
  if (is_vorg(e, s, Ein, Eout))
    return true;
  for (int u : Sadj[s])
    if (answer(e, u))
      return true;
  return false;
}

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

  vi A(Q, 0);
  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];

    A[q] = answer(Enode, Snode);
  }

  return A;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 11 ms 1620 KB Output is correct
11 Correct 11 ms 1620 KB Output is correct
12 Correct 5 ms 1496 KB Output is correct
13 Correct 4 ms 1876 KB Output is correct
14 Correct 4 ms 1876 KB Output is correct
15 Correct 19 ms 1772 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1260 ms 88836 KB Output is correct
2 Correct 635 ms 102220 KB Output is correct
3 Correct 1630 ms 97744 KB Output is correct
4 Execution timed out 4019 ms 95716 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 11 ms 1620 KB Output is correct
11 Correct 11 ms 1620 KB Output is correct
12 Correct 5 ms 1496 KB Output is correct
13 Correct 4 ms 1876 KB Output is correct
14 Correct 4 ms 1876 KB Output is correct
15 Correct 19 ms 1772 KB Output is correct
16 Correct 1260 ms 88836 KB Output is correct
17 Correct 635 ms 102220 KB Output is correct
18 Correct 1630 ms 97744 KB Output is correct
19 Execution timed out 4019 ms 95716 KB Time limit exceeded
20 Halted 0 ms 0 KB -