#include "werewolf.h"
#include <bits/stdc++.h>
#define FOR(i, n) for (int i = 0; i < n; ++i)
using namespace std;
int findIndex2Insert(vector<int> pathi, int yi) {
if (pathi.size() == 0) {
return 0;
}
int mid = 0;
int left = 0, right = pathi.size() - 1;
while (left < right) {
mid = (left + right) / 2;
if (yi <= pathi[mid]) {
right = mid;
} else {
left = mid + 1;
}
}
if (yi > pathi[left]) {
++left;
}
return left;
}
int findIndex(vector<int> pathi, int yi) {
if (pathi.size() == 0) {
return 0;
}
int mid = 0;
int left = 0, right = pathi.size() - 1;
while (left < right) {
mid = (left + right) / 2;
if (yi <= pathi[mid]) {
right = mid;
} else {
left = mid + 1;
}
}
if (yi > pathi[left] && left < pathi.size() - 1) {
++left;
} else if (yi < pathi[left] && left > 0) {
--left;
}
return left;
}
enum State {
Wolf,
Humance,
Mid
};
enum SelectState {
NoSelected,
SelectedWolf,
SelectedHumance,
SelectedBoth
};
struct Vertex {
int index;
State state;
};
State getState(int si, int li, int ri) {
if (si < li) {
return Wolf;
} else if (si > ri) {
return Humance;
} else {
return Mid;
}
}
Vertex initVertex(int index, State state) {
Vertex vertex = Vertex();
vertex.index = index;
vertex.state = state;
return vertex;
}
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();
int M = X.size();
std::vector<int> A(Q);
vector<vector<int>> path(N);
FOR(i, M) {
int xi = X[i];
int yi = Y[i];
// push Y[i] to path descendingly by using binary insert
int index = findIndex2Insert(path[xi], yi);
path[xi].insert(path[xi].begin() + index, yi);
index = findIndex2Insert(path[yi], xi);
path[yi].insert(path[yi].begin() + index, xi);
}
for (int i = 0; i < Q; ++i) {
A[i] = 0;
queue<Vertex> qVertex;
int li = L[i], ri = R[i];
vector<State> v(N);
vector<SelectState> selectedV(N);
fill(selectedV.begin(), selectedV.end(), NoSelected);
Vertex vertex = initVertex(S[i], Humance);
qVertex.push(vertex);
selectedV[S[i]] = SelectedBoth;
while (!qVertex.empty()) {
Vertex vi = qVertex.front();
qVertex.pop();
if (vi.index == E[i] && vi.state == Wolf) {
A[i] = 1;
break;
}
vector<int> vertices = path[vi.index];
if (vertices.size() == 0) { continue;}
int iLi = findIndex(vertices, li);
int iRi = findIndex(vertices, ri);
if (vi.state == Humance) {
for (int j = iRi; j < path[vi.index].size(); ++j) {
if ((selectedV[vertices[j]] == NoSelected || selectedV[vertices[j]] == SelectedWolf) && vertices[j] > ri) {
Vertex vertex = initVertex(vertices[j], Humance);
qVertex.push(vertex);
selectedV[vertices[j]] = SelectedBoth;
}
}
for (int j = iLi; j <= iRi; ++j) {
if (vertices[j] >= li && vertices[j] <= ri) {
if (selectedV[vertices[j]] == NoSelected || selectedV[vertices[j]] == SelectedWolf) {
Vertex vertex = initVertex(vertices[j], Humance);
qVertex.push(vertex);
}
if ((selectedV[vertices[j]] == NoSelected || selectedV[vertices[j]] == SelectedHumance) && vertices[j] <= ri) {
Vertex vertex = initVertex(vertices[j], Wolf);
qVertex.push(vertex);
}
selectedV[vertices[j]] = SelectedBoth;
}
}
}
if (vi.state == Wolf) {
for (int j = 0; j <= iRi; ++j) {
if (vertices[j] <= ri) {
if (selectedV[vertices[j]] == NoSelected || selectedV[vertices[j]] == SelectedHumance) {
Vertex vertex = initVertex(vertices[j], Wolf);
qVertex.push(vertex);
if (vertices[j]>= li) {
selectedV[vertices[j]] = SelectedWolf;
} else if (vertices[j] < li) {
selectedV[vertices[j]] = SelectedBoth;
}
}
}
}
}
}
}
return A;
}
Compilation message
werewolf.cpp: In function 'int findIndex(std::vector<int>, int)':
werewolf.cpp:40:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | if (yi > pathi[left] && left < pathi.size() - 1) {
| ~~~~~^~~~~~~~~~~~~~~~~~
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:119:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for (int j = iRi; j < path[vi.index].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4073 ms |
29132 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
