Submission #1239649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239649		Timosh	Werewolf (IOI18_werewolf)	C++20	15 / 100	4094 ms	29884 KiB

werewolf

#include "bits/stdc++.h"
#include "werewolf.h"

using namespace std;

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<int> vis(N), ans(L.size());
  vector<vector<int>> g(N);
  int i;
  for (int i = 0; i < X.size(); i++)
    g[X[i]].push_back(Y[i]);
  for (int i = 0; i < X.size(); i++)
    g[Y[i]].push_back(X[i]);
  auto dfs = [&](auto dfs, int node) -> void
  {
    if (node < L[i])
      return;
    vis[node] = 1;
    for (auto &x : g[node])
      if (!vis[x])
        dfs(dfs, x);
  };
  auto df = [&](auto df, int node) -> void
  {
    if (node > R[i])
      return;
    if (node >= L[i] && vis[node] == 1)
      ans[i] = 1;
    vis[node] = 2;
    for (auto &x : g[node])
      if (vis[x] != 2)
        df(df, x);
  };
  for (i = 0; i < S.size(); i++)
  {
    dfs(dfs, S[i]);
    df(df, E[i]);
    for (auto &i : vis)
      i = 0;
  }
  return ans;
}

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