oj.uz

답안 #835229

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
835229 2023-08-23T10:44:19 Z Johann 늑대인간 (IOI18_werewolf) C++14
0 / 100
 464 ms 95216 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 larger on 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];
}

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] = is_vorg(Enode, Snode, Ein, Eout);
  }

  return A;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 464 ms 95216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -