Submission #1265893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265893		canhnam357	Werewolf (IOI18_werewolf)	C++20	100 / 100	1415 ms	231888 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
struct FakeFenwick
{
  vector<vector<int>> fw, val;
  int n;
  FakeFenwick() {}
  FakeFenwick(int n) : n(n), val(n + 1, vector<int>()), fw(n + 1) {}
  bool iscc = 0;
  void fakeU(int x, int y)
  {
    iscc = 0;
    for (; x <= n; x += x & -x)
      val[x].push_back(y);
  }
  void cc()
  {
    if (iscc)
      return;
    for (int x = 1; x <= n; x++)
    {
      sort(all(val[x]));
      val[x].erase(unique(all(val[x])), val[x].end());
      fw[x].resize(val[x].size() + 1);
    }
    iscc = 1;
  }
  void update(int x, int y, int v)
  {
    assert(iscc);
    for (; x <= n; x += x & -x)
    {
      int yy = upper_bound(all(val[x]), y) - val[x].begin();
      for (; yy <= val[x].size(); yy += yy & -yy)
      {
        fw[x][yy] += v;
      }
    }
  }
  int get(int x, int y)
  {
    assert(iscc);
    int res = 0;
    for (; x; x -= x & -x)
    {
      int yy = upper_bound(all(val[x]), y) - val[x].begin();
      for (; yy; yy -= yy & -yy)
      {
        res += fw[x][yy];
      }
    }
    return res;
  }
  int get(int x1, int y1, int x2, int y2)
  {
    return get(x2, y2) - get(x2, y1 - 1) - get(x1 - 1, y2) + get(x1 - 1, y1 - 1);
  }
};
struct dsu
{
  int N, t;
  vector<vector<int>> adj, st;
  vector<int> par, pos, in, out;
  dsu() {}
  dsu(int N)
  {
    this->N = N;
    par.resize(N);
    iota(all(par), 0);
    adj.resize(N);
    pos.resize(N);
    in.resize(N);
    out.resize(N);
  }
  int find(int u)
  {
    return u == par[u] ? u : par[u] = find(par[u]);
  }
  void join(vector<int> v)
  {
    set<int> s;
    for (int i : v)
      s.insert(find(i));
    par.push_back(N);
    adj.push_back({});
    pos.push_back(-1);
    in.push_back(-1);
    out.push_back(-1);
    for (int i : s)
      par[i] = N, adj[N].push_back(i);
    N++;
  }
  void dfs(int u)
  {
    //cout << u << ' ';
    in[u] = t++;
    for (int v : adj[u])
    {
      st[v][0] = u;
      dfs(v);
    }
    out[u] = t;
    //cout << u << ' ';
  }
  void dfs()
  {
    st = vector<vector<int>>(N, vector<int>(20));
    t = 1;
    dfs(N - 1);
    st[N - 1][0] = N - 1;
    for (int i = 1; i < 20; i++)
    {
      for (int j = 0; j < N; j++) st[j][i] = st[st[j][i - 1]][i - 1];
    }
  }
  int get(int u, int k)
  {
    for (int i = 19; i >= 0; i--)
    {
      if (st[u][i] <= k) u = st[u][i];
    }
    return u;
  }
};
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
  vector<vector<int>> adj(N);
  int M = X.size();
  for (int i = 0; i < M; i++)
  {
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }
  int Q = S.size();
  vector<int> res(Q);
  dsu dsuL(N), dsuR(N);
  for (int i = N - 1; i >= 0; i--)
  {
    vector<int> v = {i};
    for (int j : adj[i])
      if (j > i)
        v.push_back(j);
    dsuL.join(v);
  }
  for (int i = 0; i < N; i++)
  {
    vector<int> v = {i};
    for (int j : adj[i])
      if (j < i)
        v.push_back(j);
    dsuR.join(v);
  }
  //out << "LEFT ";
  dsuL.dfs();
  //cout << "\nRIGHT ";
  dsuR.dfs();
  //cout << '\n';
  FakeFenwick tree(N + M + 5);
  for (int i = 0; i < N; i++)
  {
    int x = dsuL.in[i], y = dsuR.in[i];
    //cout << x << ' ' << y << '\n';
    tree.fakeU(x, y);
  }
  tree.cc();
  for (int i = 0; i < N; i++)
  {
    int x = dsuL.in[i], y = dsuR.in[i];
    tree.update(x, y, 1);
  }
  for (int i = 0; i < Q; i++)
  {
    int f = dsuL.get(S[i], 2 * N - 1 - L[i]), s = dsuR.get(E[i], N + R[i]);
    int lx = dsuL.in[f], rx = dsuL.out[f] - 1;
    int ly = dsuR.in[s], ry = dsuR.out[s] - 1;
    //cout << lx << ' ' << rx << ' ' << ly << ' ' << ry << ' ' << tree.get(lx, ly, rx, ry) << '\n';
    res[i] = (tree.get(lx, ly, rx, ry) > 0);
  }
  return res;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51