Submission #602086

#	Time	Username	Problem	Language	Result	Execution time	Memory
602086		erekle	Werewolf (IOI18_werewolf)	C++17	15 / 100	335 ms	11656 KiB

werewolf

#include "werewolf.h"
#include <queue>
#include <iostream>

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) {
  int M = X.size(), Q = S.size();
  vector<int> A(Q);
  
  if (N <= 3000 && M <= 6000 && Q <= 3000) { // subtasks 1 and 2
    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]);
    }
    for (int qq = 0; qq < Q; ++qq) {
      cerr << " ON QUERY " << qq << endl;
      int s = S[qq], e = E[qq], l = L[qq], r = R[qq];

      // bfs from start as human
      cerr << " BFS FROM S" << endl;
      vector<bool> canHuman(N);
      queue<int> q;
      q.push(s), canHuman[s] = true;
      while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y : g[x]) {
          if (!canHuman[y] && y >= l) q.push(y), canHuman[y] = true;
        }
      }

      cerr << " BFS FROM E" << endl;
      vector<bool> canWolf(N);
      q.push(e), canWolf[e] = true;
      while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y : g[x]) {
          if (!canWolf[y] && y <= r) q.push(y), canWolf[y] = true;
        }
      }

      for (int i = 0; i < N; ++i) {
        if (canHuman[i] && canWolf[i] && l <= i && i <= r) A[qq] = 1;
      }
    }
  }

  return A;
}

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