Submission #250516

#	Time	Username	Problem	Language	Result	Execution time	Memory
250516		fedoseevtimofey	Werewolf (IOI18_werewolf)	C++14	15 / 100	4050 ms	32080 KiB

werewolf

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

#include "werewolf.h"

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) {
  vector <vector <int>> g(n);
  for (int i = 0; i < (int)x.size(); ++i) {
    g[x[i]].push_back(y[i]);
    g[y[i]].push_back(x[i]);
  }
  int q = s.size();
  vector <int> ans(q);
  for (int i = 0; i < q; ++i) {
    vector <int> go_s(n), go_e(n);
    queue <int> q;
    if (s[i] >= l[i]) {
      q.push(s[i]);
      go_s[s[i]] = 1;
    }
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (auto v : g[u]) {
        if (!go_s[v] && v >= l[i]) {
          go_s[v] = 1;
          q.push(v);
        }   
      }   
    }
    while (!q.empty()) q.pop();
    if (e[i] <= r[i]) {
      q.push(e[i]);
      go_e[e[i]] = 1;
    }
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (auto v : g[u]) {
        if (!go_e[v] && v <= r[i]) {
          go_e[v] = 1;
          q.push(v);
        }
      }
    }
    bool ok = false;
    for (int i = 0; i < n; ++i) {
      ok |= (go_s[i] && go_e[i]);
    }
    ans[i] = ok;
  } 
  return ans;
}

#ifdef LOCAL
namespace {
int read_int() {
  int x;
  cin >> x;
  return x;
}

}  // namespace

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int N = read_int();
  int M = read_int();
  int Q = read_int();
  std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
  for (int j = 0; j < M; ++j) {
    X[j] = read_int();
    Y[j] = read_int();
  }
  for (int i = 0; i < Q; ++i) {
    S[i] = read_int();
    E[i] = read_int();
    L[i] = read_int();
    R[i] = read_int();
  }

  std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
  for (size_t i = 0; i < A.size(); ++i) {
    printf("%d\n", A[i]);
  }
}
#endif

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