# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1241408 | vivkostov | Werewolf (IOI18_werewolf) | C++20 | 0 ms | 0 KiB |
//#pragma once
//#include "werewolf.h"
#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
int n,m,q,a[200005],b[200005],l[200005],r[200005],used1[3005],used2[3005],lamp;
vector<int>v[200005],otg;
void dfs1(int beg,int l)
{
used1[beg]=1;
int w;
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i];
if(w>=l&&!used1[w])dfs1(w,l);
}
}
void dfs2(int beg,int l,int r)
{
used2[beg]=1;
if(used1[beg])
{
if(beg>=l&&beg<=r)lamp=1;
}
int w;
for(int i=0;i<v[beg].size();i++)
{
w=v[beg][i];
if(w<=r&&!used2[w])dfs2(w,l,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)
{
n=N;
m=X.size();
q=S.size();
for(int i=1;i<=m;i++)
{
v[X[i-1]+1].push_back(Y[i-1]+1);
v[Y[i-1]+1].push_back(X[i-1]+1);
}
for(int i=1;i<=q;i++)
{
a[i]=S[i-1]+1;
b[i]=E[i-1]+1;
l[i]=L[i-1]+1;
r[i]=R[i-1]+1;
memset(used1,0,sizeof(used1));
memset(used2,0,sizeof(used2));
lamp=0;
dfs1(a[i],l[i]);
dfs2(b[i],l[i],r[i]);
otg.push_back(lamp);
}
return otg;
}