Submission #1043002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043002		thatsgonzalez	Werewolf (IOI18_werewolf)	C++14	15 / 100	166 ms	51840 KiB

werewolf

#include <bits/stdc++.h>
 
using namespace std;
 
const int nmax = 1e5+100;
 
vector<vector<int>> g;
bitset <nmax> vis1, vis2;
bool res = false;
 
 
void dfs(int node, int l, int r, bool estado){
  if(!estado and node<l) return;
  if(estado and node>r) return;
 
  /*if(!estado)*/ vis1[node] = 1;
  //else vis2[node] = 1;
 
  for(auto &x: g[node]){
    if(vis1[x] /*and !estado*/) continue;
    //if(vis2[x] and estado) continue;
 
    /*if(x>=l and x<=r and !estado){
      dfs(x,endpoint,l,r,estado);
      dfs(x,endpoint,l,r,!estado);
    }
    else{*/
      dfs(x,l,r,estado);
    //}
 
  }
 
}
 
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 Q = S.size();
  int M = X.size();
  std::vector<int> ans(Q,0);
 
  g.resize(N);
  
  for(int i = 0; i<M; i++){
 
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
 
  }

  bitset<nmax> a,b;
 
  for(int q = 0; q<Q; q++){
 
    res = false;

    dfs(S[q],L[q],R[q],0);
    a = vis1;
    vis1.reset();
    dfs(E[q],L[q],R[q],1);
    b = vis1;
    vis1.reset();

    for(int i = 0; i<N; i++){
        if(a[i] and b[i]) {
            res = true; break;
        }
    }


    ans[q] = res;
    //vis2.reset();
 
  }
  g.clear();
 
  return ans;
}

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