Submission #443046

#	Time	Username	Problem	Language	Result	Execution time	Memory
443046		peijar	Werewolf (IOI18_werewolf)	C++17	100 / 100	998 ms	167660 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5;
const int MAXP = 18;

vector<int> adj[MAXN], adjMin[MAXN], adjMax[MAXN];
vector<int> S, E;
int tin[MAXN], tout[MAXN];
int curTime;
int parMin[MAXP][MAXN], parMax[MAXP][MAXN];
int nbSommets, nbAretes, nbRequetes;
vector<int> ans;
vector<int> queryAtNode[MAXN];
int idMin[MAXN], largestMin[MAXN], idMax[MAXN], smallestMax[MAXN];

void dfs(int u) {
  tin[u] = curTime++;
  for (int v : adjMin[u])
    dfs(v);
  tout[u] = curTime++;
}

set<int> dfs2(int u) {
  vector<set<int>> childs = {{tin[u]}};
  for (int v : adjMax[u]) {
    childs.push_back(dfs2(v));
  }
  for (int i = 1; i < (int)childs.size(); ++i)
    if (childs[i].size() > childs[0].size())
      swap(childs[i], childs[0]);
  for (int i = 1; i < (int)childs.size(); ++i)
    for (auto v : childs[i])
      childs[0].insert(v);
  set<int> ret = move(childs[0]);
  for (int iRequete : queryAtNode[u]) {
    auto it = ret.lower_bound(tin[S[iRequete]]);
    if (it != ret.end() and *it <= tout[S[iRequete]])
      ans[iRequete] = 1;
  }
  return ret;
}

// Min tree : We want the minimum vertex on a path to be the largest possible.

int findMin(int u) { return idMin[u] < 0 ? u : idMin[u] = findMin(idMin[u]); }

int findMax(int u) { return idMax[u] < 0 ? u : idMax[u] = findMax(idMax[u]); }

void mergeMin(int a, int b) {
  a = findMin(a), b = findMin(b);
  if (a == b)
    return;
  if (largestMin[a] < largestMin[b])
    swap(a, b);
  parMin[0][largestMin[a]] = largestMin[b];
  adjMin[largestMin[b]].push_back(largestMin[a]);
  idMin[a] += idMin[b];
  idMin[b] = a;
  largestMin[a] = largestMin[b];
}

void mergeMax(int a, int b) {
  a = findMax(a), b = findMax(b);
  if (a == b)
    return;
  if (smallestMax[a] > smallestMax[b])
    swap(a, b);
  parMax[0][smallestMax[a]] = smallestMax[b];
  adjMax[smallestMax[b]].push_back(smallestMax[a]);
  idMax[a] += idMax[b];
  idMax[b] = a;
  smallestMax[a] = smallestMax[b];
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> _S,
                           vector<int> _E, vector<int> L, vector<int> R) {
  S = _S, E = _E;
  nbSommets = N;
  nbAretes = X.size();
  for (int i = 0; i < nbAretes; ++i) {
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }
  for (int i = 0; i < nbSommets; ++i) {
    largestMin[i] = smallestMax[i] = i;
    idMin[i] = idMax[i] = -1;
  }
  for (int i = nbSommets - 1; i >= 0; --i)
    for (int j : adj[i])
      if (j > i) {
        mergeMin(j, i);
      }
  for (int i = 0; i < nbSommets; ++i)
    for (int j : adj[i])
      if (j < i)
        mergeMax(j, i);
  parMax[0][nbSommets - 1] = nbSommets - 1;

  for (int p = 0; p < MAXP - 1; ++p)
    for (int i = 0; i < nbSommets; ++i) {
      parMax[p + 1][i] = parMax[p][parMax[p][i]];
      parMin[p + 1][i] = parMin[p][parMin[p][i]];
    }

  nbRequetes = S.size();
  for (int i = 0; i < nbRequetes; ++i)
    for (int p = MAXP - 1; p >= 0; --p)
      if (parMin[p][S[i]] >= L[i])
        S[i] = parMin[p][S[i]];
  ans.resize(nbRequetes);

  for (int i = 0; i < nbRequetes; ++i)
    for (int p = MAXP - 1; p >= 0; --p)
      if (parMax[p][E[i]] <= R[i])
        E[i] = parMax[p][E[i]];
  for (int i = 0; i < nbRequetes; ++i)
    queryAtNode[E[i]].push_back(i);
  dfs(0);
  dfs2(nbSommets - 1);
  return ans;
}

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