Submission #1238404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238404		noyancanturk	Werewolf (IOI18_werewolf)	C++20	15 / 100	4091 ms	26200 KiB

werewolf

#include "werewolf.h"

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

#define pb push_back

using pii=pair<int,int>;

const int lim=2e5+100;

vector<int>v[lim];

int vis1[lim],vis2[lim];

void dfs1(int node,int nope){
  vis1[node]=1;
  for(int j:v[node]){
    if(j<nope||vis1[j])continue;
    dfs1(j,nope);
  }
}

void dfs2(int node,int nope){
  vis2[node]=1;
  for(int j:v[node]){
    if(nope<j||vis2[j])continue;
    dfs2(j,nope);
  }
}

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 m=X.size();
  int q=s.size();
  for(int i=0;i<m;i++){
    v[X[i]].pb(Y[i]);
    v[Y[i]].pb(X[i]);
  }
  vector<int>ans(q);
  for(int i=0;i<q;i++){
    for(int j=0;j<n;j++){
      vis1[j]=vis2[j]=0;
    }
    dfs1(s[i],L[i]);
    dfs2(e[i],R[i]);
    for(int j=0;j<n;j++){
      ans[i]|=vis1[j]&&vis2[j];
    }
  }
  return ans;
}

// 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();
//   std::vector<int> A(Q);
//   for (int i = 0; i < Q; ++i) {
//     A[i] = 0;
//   }
//   return A;
// }

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