Submission #815404

#	Time	Username	Problem	Language	Result	Execution time	Memory
815404		erray	Werewolf (IOI18_werewolf)	C++17	15 / 100	4101 ms	23152 KiB

werewolf

#include "werewolf.h"
//author: erray
#include <bits/stdc++.h>

using namespace std;
 
#ifdef DEBUG
  #include "/home/ioi/codes/debug.h"
#else
  #define debug(...) (void) 37
#endif

struct DSU {
  vector<int> link;
  DSU(int n) {
    link.resize(n);
    iota(link.begin(), link.end(), 0);
  }
  int get(int v) {
    return link[v] = (v == link[v] ? v : get(link[v]));
  }
  bool unite(int x, int y) {
    x = get(x), y = get(y);
    if (x == y) {
      return false;
    }
    link[y] = x;
    return true;
  }
};
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) {
  int M = int(X.size());
  int Q = int(E.size());
  vector<vector<int>> g(N);
  for (int i = 0; i < M; ++i) {
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }
  vector<int> ans(Q);
  for (int q = 0; q < Q; ++q) {
    DSU eg(N), sg(N);
    for (int i = 0; i <= R[q]; ++i) {
      for (auto u : g[i]) {
        if (u < i) {
          eg.unite(i, u);
        }
      }
    }
    for (int i = N - 1; i >= L[q]; --i) {
      for (auto u : g[i]) {
        if (u > i) {
          sg.unite(i, u);
        }
      }
    }
    for (int i = 0; i < N; ++i) {
      ans[q] |= (eg.get(i) == eg.get(E[q]) && sg.get(i) == sg.get(S[q]));
    }
  }
  return ans;
}

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