Submission #289661

#	Time	Username	Problem	Language	Result	Execution time	Memory
289661		DanerZein	Werewolf (IOI18_werewolf)	C++14	0 / 100	4075 ms	38196 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int l,r;
bitset<200010> vh,vw;
vector<vi> G;
set<int> h,w;
void dfs_human(int u){
  if(u<l) return;
  vh[u]=1;
  h.insert(u);
  for(auto &v:G[u]){
    if(!vh[v]){
      dfs_human(v);
    }
  }
  vh[u]=0;
}
void dfs_wolf(int u){
  if(u>r) return;
  vw[u]=1;
  w.insert(u);
  for(auto &v:G[u]){
    if(!vw[v]){
      dfs_wolf(v);
    }
  }
  vw[u]=0;
}
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) {
  G.resize(N+1);
  for(int i=0;i<X.size();i++){
    int u=X[i],v=Y[i];
    G[u].push_back(v);
    G[v].push_back(u);
  }
  vector<int> res;
  for(int i=0;i<S.size();i++){
    h.clear();
    w.clear();
    l=L[i];
    r=R[i];
    dfs_human(S[i]);
    dfs_wolf(E[i]);
    bool sw=0;
    for(auto &v:h){
      if(binary_search(w.begin(),w.end(),v)){
	sw=1;
	break;
      }
    }
    res.push_back(sw);
  }
  return res;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:35:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int i=0;i<X.size();i++){
      |               ~^~~~~~~~~
werewolf.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int i=0;i<S.size();i++){
      |               ~^~~~~~~~~

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