oj.uz

Submission #835286

# Submission time Handle Problem Language Result Execution time Memory
835286 2023-08-23T11:44:53 Z Johann Werewolf (IOI18_werewolf) C++14
100 / 100
 795 ms 180532 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(nodes[u], nodes[v]);
      for (int x : nodes[u])
        nodes[v].insert(x);
    }

  for (pii tmp : tocheck[v])
  {
    int s, q;
    tie(s, q) = tmp;
    auto it = nodes[v].lower_bound(Sin[s]);
    if (it == nodes[v].end())
      A[q] = 0;
    else
    {
      int lb = *it;
      assert(lb >= Sin[s]);
      A[q] = (lb < 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);
  nodes.assign(N, set<int>());
  answer(N - 1, N - 1);

  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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 5 ms 2260 KB Output is correct
11 Correct 5 ms 2260 KB Output is correct
12 Correct 6 ms 2388 KB Output is correct
13 Correct 5 ms 2388 KB Output is correct
14 Correct 7 ms 2388 KB Output is correct
15 Correct 7 ms 2388 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 171648 KB Output is correct
2 Correct 639 ms 136412 KB Output is correct
3 Correct 567 ms 136288 KB Output is correct
4 Correct 567 ms 142344 KB Output is correct
5 Correct 614 ms 152156 KB Output is correct
6 Correct 629 ms 158772 KB Output is correct
7 Correct 739 ms 180532 KB Output is correct
8 Correct 662 ms 145028 KB Output is correct
9 Correct 489 ms 144720 KB Output is correct
10 Correct 444 ms 150260 KB Output is correct
11 Correct 468 ms 151680 KB Output is correct
12 Correct 525 ms 158784 KB Output is correct
13 Correct 791 ms 152380 KB Output is correct
14 Correct 770 ms 152384 KB Output is correct
15 Correct 769 ms 152340 KB Output is correct
16 Correct 730 ms 152440 KB Output is correct
17 Correct 742 ms 179784 KB Output is correct

Subtask #4
51.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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 5 ms 2260 KB Output is correct
11 Correct 5 ms 2260 KB Output is correct
12 Correct 6 ms 2388 KB Output is correct
13 Correct 5 ms 2388 KB Output is correct
14 Correct 7 ms 2388 KB Output is correct
15 Correct 7 ms 2388 KB Output is correct
16 Correct 731 ms 171648 KB Output is correct
17 Correct 639 ms 136412 KB Output is correct
18 Correct 567 ms 136288 KB Output is correct
19 Correct 567 ms 142344 KB Output is correct
20 Correct 614 ms 152156 KB Output is correct
21 Correct 629 ms 158772 KB Output is correct
22 Correct 739 ms 180532 KB Output is correct
23 Correct 662 ms 145028 KB Output is correct
24 Correct 489 ms 144720 KB Output is correct
25 Correct 444 ms 150260 KB Output is correct
26 Correct 468 ms 151680 KB Output is correct
27 Correct 525 ms 158784 KB Output is correct
28 Correct 791 ms 152380 KB Output is correct
29 Correct 770 ms 152384 KB Output is correct
30 Correct 769 ms 152340 KB Output is correct
31 Correct 730 ms 152440 KB Output is correct
32 Correct 742 ms 179784 KB Output is correct
33 Correct 739 ms 150520 KB Output is correct
34 Correct 198 ms 37904 KB Output is correct
35 Correct 764 ms 147324 KB Output is correct
36 Correct 711 ms 153648 KB Output is correct
37 Correct 734 ms 146836 KB Output is correct
38 Correct 740 ms 151256 KB Output is correct
39 Correct 717 ms 156068 KB Output is correct
40 Correct 769 ms 155016 KB Output is correct
41 Correct 584 ms 145696 KB Output is correct
42 Correct 560 ms 151732 KB Output is correct
43 Correct 777 ms 152764 KB Output is correct
44 Correct 623 ms 146336 KB Output is correct
45 Correct 566 ms 156912 KB Output is correct
46 Correct 573 ms 156628 KB Output is correct
47 Correct 781 ms 152472 KB Output is correct
48 Correct 795 ms 152412 KB Output is correct
49 Correct 766 ms 152508 KB Output is correct
50 Correct 778 ms 152444 KB Output is correct
51 Correct 701 ms 154076 KB Output is correct
52 Correct 716 ms 154052 KB Output is correct