# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
295558 | eohomegrownapps | Werewolf (IOI18_werewolf) | C++14 | 4074 ms | 22368 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>
using namespace std;
int n,q;
vector<vector<int>> adjlist;
vector<int> cnt;
int maxcnt = 0;
void bfs(int start, int l, int r, bool human){
queue<int> q;
vector<bool> visited(n);
visited[start]=true;
q.push(start);
while (q.size()>0){
int f = q.front();
q.pop();
for (int i : adjlist[f]){
if (visited[i]){continue;}
if ((human&&i<l)||((!human)&&i>r)){continue;}
cnt[i]++;
maxcnt=max(maxcnt,cnt[i]);
visited[i]=true;
q.push(i);
}
}
}
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) {
q = s.size();
n=N;
adjlist.resize(n);
for (int i = 0; i<x.size(); i++){
//cout<<x[i]<<' '<<y[i]<<endl;
adjlist[x[i]].push_back(y[i]);
adjlist[y[i]].push_back(x[i]);
}
vector<int> ans(q,0);
for (int i = 0; i<q; i++){
cnt.assign(n,0);
maxcnt=0;
bfs(s[i],L[i],R[i],true);
bfs(e[i],L[i],R[i],false);
if (maxcnt==2){
ans[i]=1;
}
}
return ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |