oj.uz

Submission #600832

# Submission time Handle Problem Language Result Execution time Memory
600832 2022-07-21T08:08:52 Z Mamedov Werewolf (IOI18_werewolf) C++17
15 / 100
 1045 ms 524288 KB 
#pragma GCC optimize ("O3")
#include "werewolf.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct DSU {
  int components;
  vector<int>par;
  DSU(int n) {
    par.assign(n, -1);
    components = n;
  }
  int Find(int u) {
    if (par[u] < 0) return u;
    else return par[u] = Find(par[u]);
  }
  bool Union(int u, int v) {
    u = Find(u);
    v = Find(v);
    if (u != v) {
      par[u] += par[v];
      par[v] = u;
      --components;
      return true;
    } else {
      return false;
    }
  }
};

void dfs1(int node, vvi &tree, int &tmr, vi &tin, vi &tout) {
  tin[node] = ++tmr;
  for (int to : tree[node]) {
    dfs1(to, tree, tmr, tin, tout);
  }
  tout[node] = tmr;
}

void dfs2(int node, vvi &tree, vi &tin, vi &tout, vvpii &group, vector<set<int>> &subTree, vi &res) {
  int maxChild = -1;
  for (int to : tree[node]) {
    dfs2(to, tree, tin, tout, group, subTree, res);
    if (maxChild == -1 || size(subTree[to]) > size(subTree[maxChild])) {
      maxChild = to;
    }
  }
  if (maxChild != -1) {
    subTree[node] = subTree[maxChild];
    for (int to : tree[node]) {
      if (to != maxChild) {
        subTree[node].insert(all(subTree[to]));
      }
    }
  }
  subTree[node].insert(tin[node]);
  for (auto [v, i] : group[node]) {
    auto itr = subTree[node].lower_bound(tin[v]);
    if (itr != subTree[node].end() && (*itr) <= tout[v]) {
      res[i] = 1;
    }
  }
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
  int M = size(X);
  vvi g(N);
  for (int i = 0; i < M; ++i) {
    g[X[i]].eb(Y[i]);
    g[Y[i]].eb(X[i]);
  }

  DSU dsu1(N), dsu2(N);
  vvi treeHuman(N), treeWolf(N);
  vector<vvi>up(2, vvi(19, vi(N)));

  up[0][0][0] = 0;
  for (int i = N - 1; i >= 0; --i) {
    for (int to : g[i]) {
      if (to > i && dsu1.Find(to) != i) {
        treeHuman[i].eb(dsu1.Find(to));
        up[0][0][dsu1.Find(to)] = i;
        dsu1.Union(i, to);
      }
    }
  }
  up[1][0][N - 1] = N - 1;
  for (int i = 0; i < N; ++i) {
    for (int to : g[i]) {
      if (to < i && dsu2.Find(to) != i) {
        treeWolf[i].eb(dsu2.Find(to));
        up[1][0][dsu2.Find(to)] = i;
        dsu2.Union(i, to);
      }
    }
  }
  for (int k = 0; k < 2; ++k) {
    for (int i = 1; i < 19; ++i) {
      for (int j = 0; j < N; ++j) {
        up[k][i][j] = up[k][i - 1][up[k][i - 1][j]];
      }
    }
  }
  int Q = size(S);
  vvpii group(N);
  for (int i = 0; i < Q; ++i) {
    for (int j = 18; j >= 0; --j) {
      if (up[0][j][S[i]] >= L[i]) {
        S[i] = up[0][j][S[i]];
      }
      if (up[1][j][E[i]] <= R[i]) {
        E[i] = up[1][j][E[i]];
      }
    }
    group[E[i]].eb(mpr(S[i], i));
  }

  int tmr = -1;
  vi tin(N), tout(N);
  dfs1(0, treeHuman, tmr, tin, tout);

  vi res(Q, 0);
  vector<set<int>>subTree(N);
  dfs2(N - 1, treeWolf, tin, tout, group, subTree, res);
  return res;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 1 ms 428 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 132 ms 79928 KB Output is correct
11 Correct 80 ms 49928 KB Output is correct
12 Correct 8 ms 3668 KB Output is correct
13 Correct 319 ms 213712 KB Output is correct
14 Correct 330 ms 213792 KB Output is correct
15 Correct 95 ms 57056 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1045 ms 320892 KB Output is correct
2 Runtime error 901 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 1 ms 428 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 132 ms 79928 KB Output is correct
11 Correct 80 ms 49928 KB Output is correct
12 Correct 8 ms 3668 KB Output is correct
13 Correct 319 ms 213712 KB Output is correct
14 Correct 330 ms 213792 KB Output is correct
15 Correct 95 ms 57056 KB Output is correct
16 Correct 1045 ms 320892 KB Output is correct
17 Runtime error 901 ms 524288 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -