Submission #690492

#	Time	Username	Problem	Language	Result	Execution time	Memory
690492		zeroesandones	Werewolf (IOI18_werewolf)	C++17	15 / 100	261 ms	29640 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;

using ll = long long;
using vi = vector<ll>;

#define pb push_back

const int mxN = 3005;
vi adj[mxN];
bool vis1[mxN];
bool vis2[mxN];

void dfs1(int x, int l) {
  vis1[x] = true;
  for(auto y : adj[x]) {
    if(!vis1[y] && y >= l) {
      dfs1(y, l);
    }
  }
}

void dfs2(int x, int r) {
  vis2[x] = true;
  for(auto y : adj[x] ){
    if(!vis2[y] && y <= r) {
      dfs2(y, r);
    }
  }
}

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 Q = S.size();
  vector<int> A(Q);
  for(int i = 0; i < (int) X.size(); ++i) {
    adj[X[i]].pb(Y[i]);
    adj[Y[i]].pb(X[i]);
  }

  for(int i = 0; i < Q; ++i) {
    memset(vis1, false, sizeof(vis1));
    memset(vis2, false, sizeof(vis2));
    dfs1(S[i], L[i]);
    dfs2(E[i], R[i]);
    bool pos = false;
    for(int j = L[i]; j <= R[i]; ++j) {
      if(vis1[j] && vis2[j]) {
        pos = true;
        break;
      }
    }
    A[i] = (pos ? 1 : 0);
  }

  return A;
}

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