Submission #282932

#	Time	Username	Problem	Language	Result	Execution time	Memory
282932		milleniumEeee	Werewolf (IOI18_werewolf)	C++14	15 / 100	371 ms	54008 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;
typedef vector<int> vi;

const int MAXN = (int)2e5 + 5;
const int MAXM = (int)4e5 + 5;
const int MAXQ = (int)2e5 + 5;

vector <int> g[MAXN];
int N, M, Q;

struct Query {
  int s, e, l, r; 
  Query (int s_, int e_, int l_, int r_) {
    s = s_, e = e_, l = l_, r = r_;
  }
  Query () {

  }
}query[MAXQ];

struct Small_Solve {
  bool need = false;
  vector <int> ans;
  void solve() {
    ans.resize(Q, 0);
    vector <int> used[3];
    used[1].resize(N, 0);
    used[2].resize(N, 0);
    int cnt = 0;
    for (int i = 0; i < Q; i++) {
      cnt++;
      queue <int> q[3];
      if (query[i].s >= query[i].l) {
        q[1].push(query[i].s);
      }
      if (query[i].e <= query[i].r) {
        q[2].push(query[i].e);
      }
      while (!q[1].empty()) {
        int v = q[1].front();
        q[1].pop();
        if (used[1][v] == cnt) {
          continue;
        }
        used[1][v] = cnt;
        for (int to : g[v]) {
          if (to >= query[i].l) {
            q[1].push(to);
          }
        }
      }
      while (!q[2].empty()) {
        int v = q[2].front();
        q[2].pop();
        if (used[2][v] == cnt) {
          continue;
        }
        used[2][v] = cnt;
        for (int to : g[v]) {
          if (to <= query[i].r) {
            q[2].push(to);
          }
        }
      }
      int found = 0;
      for (int v = 0; v < N; v++) {
        found |= (used[1][v] == cnt && used[2][v] == cnt);
      }
      ans[i] = found;
    }
  }
}subtask12;

bool bambook() {
  return false;
}

std::vector<int> check_validity(int NN, vi X, vi Y, vi S, vi E, vi L, vi R) {
  N = NN;
  M = szof(X);
  Q = szof(S);
  for (int i = 0; i < M; i++) {
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }
  for (int i = 0; i < Q; i++) {
    query[i] = Query(S[i], E[i], L[i], R[i]);
  }
  if (N <= 3000 && M <= 6000 && Q <= 3000) {
    subtask12.need = true;
    subtask12.solve();
    return subtask12.ans;
  }
  else if (bambook() == true) {
    
  }
  assert(false);
}

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