# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
600800 | enerelt14 | Werewolf (IOI18_werewolf) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "werewolf.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
bool vis[3005], is[3005];
vector<int>adj[3005];
void dijkstra1(int s, int l){
queue<int>pq;
pq.push(s);
while(!pq.empty()){
int u=pq.front();
pq.pop();
vis[u]=1;
for (int i=0;i<adj[u].size();i++){
if (adj[u][i]<l || vis[adj[u][i]])continue;
pq.push(adj[u][i]);
}
while(!pq.empty() && vis[pq.front()])pq.pop();
}
}
void dijkstra2(int s, int r){
queue<int>pq;
pq.push(s);
while(!pq.empty()){
int u=pq.front();
pq.pop();
vis[u]=1;
for (int i=0;i<adj[u].size();i++){
if (adj[u][i]>r || vis[adj[u][i]])continue;
pq.push(adj[u][i]);
}
while(!pq.empty() && vis[pq.front()])pq.pop();
}
}
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:
for (int i=0;i<X.size();i++){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
int Q=S.size();
vector<int>ans;
for (int i=0;i<Q;i++){
ans[i]=0;
if (S[i]<L[i] || E[i]>R[i])continue;
for (int i=L[i];i<n;i++)vis[i]=0;
dijkstra1(S[i], L[i]);
for (int i=L[i];i<=R[i];i++)is[i]=vis[i];
for (int i=0;i<=R[i];i++)vis[i]=0;
dijkstra2(E[i], R[i]);
for (int i=L[i];i<=R[i];i++){
if (vis[i] && is[i]){
ans[i]=1;
break;
}
}
}
return ans;
}