#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;
void dfsHuman(int u, int N, vector<vector<int>> &adj, vector<bool> &humanReach, int curL) {
if (humanReach[u] || u < curL) return;
humanReach[u] = true;
for (int v: adj[u]) {
dfsHuman(v,N,adj,humanReach,curL);
}
}
void dfsWolf(int u, int N, vector<vector<int>> &adj, vector<bool> &wolfReach, int curR) {
if (wolfReach[u] || u > curR) return;
wolfReach[u] = true;
for (int v: adj[u]) {
dfsWolf(v,N,adj,wolfReach,curR);
}
}
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();
vector<vector<int>> adj(N);
for (int i = 0; i < X.size(); i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
vector<int> A(Q,0);
for (int q = 0; q < Q; q++) {
//S[q],E[q],L[q],R[q]
vector<bool> humanReach(N,false), wolfReach(N,false);
dfsHuman(S[q],N,adj,humanReach,L[q]);
dfsWolf(E[q],N,adj,wolfReach,R[q]);
bool connected = false;
for (int i = 0; i < N; i++) {
if (humanReach[i] && wolfReach[i]) {
connected = true;
// cerr << i << "\n";
}
}
A[q] = connected;
}
return A;
}
Compilation message
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:30:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < X.size(); i++) {
~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
128 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
128 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
340 ms |
820 KB |
Output is correct |
11 |
Correct |
231 ms |
860 KB |
Output is correct |
12 |
Correct |
29 ms |
896 KB |
Output is correct |
13 |
Correct |
368 ms |
892 KB |
Output is correct |
14 |
Correct |
237 ms |
888 KB |
Output is correct |
15 |
Correct |
350 ms |
1068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4019 ms |
32180 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
128 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
340 ms |
820 KB |
Output is correct |
11 |
Correct |
231 ms |
860 KB |
Output is correct |
12 |
Correct |
29 ms |
896 KB |
Output is correct |
13 |
Correct |
368 ms |
892 KB |
Output is correct |
14 |
Correct |
237 ms |
888 KB |
Output is correct |
15 |
Correct |
350 ms |
1068 KB |
Output is correct |
16 |
Execution timed out |
4019 ms |
32180 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |