#include "werewolf.h"
#include <bits/stdc++.h>
#define sz(x) ((x).size())
using namespace std;
const int inf = 1e9;
const int p2 = 1<<18;
struct Segtree {
Segtree() {
t = new int [p2*2];
for (int i = 0; i < p2*2; i++) t[i] = -inf;
}
~Segtree() {
delete [] t;
}
void upd(int x, int v) {
for (x += p2; x; x /= 2) {
t[x] = max(t[x], v);
}
}
int get(int b, int e) {
int r = -inf;
b += p2;
e += p2;
while (b <= e) {
if (b%2 == 1) {
r = max(r, t[b]);
b++;
}
if (e%2 == 0) {
r = max(r, t[e]);
e--;
}
b /= 2;
e /= 2;
}
return r;
}
int* t;
};
vector<int> calc(const int n, std::vector<int> edgeX, std::vector<int> edgeY, std::vector<int> queryX, std::vector<int> queryY, std::vector<int> queryLB, std::vector<int> queryRB, bool sw = false) {
vector<int> graph [n];
for (int i = 0; i < sz(edgeX); i++) {
graph[edgeX[i]].push_back(edgeY[i]);
graph[edgeY[i]].push_back(edgeX[i]);
}
vector<int> path;
for (int i = 0; i < n; i++) if (sz(graph[i]) == 1) {
bool vis [n];
for (int j = 0; j < n; j++) vis[j] = false;
int x = i;
while (1) {
vis[x] = true;
path.push_back(x);
bool ch = false;
for (int y : graph[x]) if (!vis[y]) {
x = y;
ch = true;
break;
}
if (!ch) {
break;
}
}
break;
}
assert(sz(path) == n);
if (sw) {
reverse(path.begin(), path.end());
}
int invPath [n];
for (int i = 0; i < n; i++) invPath[path[i]] = i;
const int nbQ = sz(queryX);
for (int i = 0; i < nbQ; i++) {
queryX[i] = invPath[queryX[i]];
queryY[i] = invPath[queryY[i]];
}
vector<int> queriesSmallerThan [n];
int latestPerQuery [nbQ];
vector<int> queriesBiggerThan [n];
int earliestPerQuery [nbQ];
for (int i = 0; i < nbQ; i++) {
if (queryLB[i] >= 1) {
queriesSmallerThan[queryLB[i] - 1].push_back(i);
}
else {
latestPerQuery[i] = -1;
}
if (queryRB[i]+1 < n) {
queriesBiggerThan[queryRB[i] + 1].push_back(i);
}
else {
earliestPerQuery[i] = n;
}
}
Segtree st = Segtree();
for (int i = 0; i < n; i++) {
st.upd(invPath[i], invPath[i]);
for (int j : queriesSmallerThan[i]) {
latestPerQuery[j] = st.get(queryX[j], queryY[j]);
}
}
st = Segtree();
for (int i = n-1; i >= 0; i--) {
st.upd(invPath[i], -invPath[i]);
for (int j : queriesBiggerThan[i]) {
earliestPerQuery[j] = -st.get(queryX[j], queryY[j]);
}
}
vector<int> res(nbQ);
vector<int> askPref [nbQ];
for (int i = 0; i < nbQ; i++) {
if (queryX[i] > queryY[i]) {
res[i] = -1;
}
else {
res[i] = 0;
int x = min(earliestPerQuery[i]-1, n-1);
// assert(0 <= x && x < n);
askPref[x].push_back(i);
}
}
st = Segtree();
for (int i = 0; i < n; i++) {
st.upd(path[i], i);
for (int j : askPref[i]) {
int loc = st.get(queryLB[j], queryRB[j]);
if (loc >= latestPerQuery[j]+1) {
res[j] = 1;
}
else {
res[j] = -1;
}
}
}
return res;
}
std::vector<int> check_validity(const int n, std::vector<int> edgeX, std::vector<int> edgeY, std::vector<int> queryX, std::vector<int> queryY, std::vector<int> queryLB, std::vector<int> queryRB) {
vector<int> resA = calc(n, edgeX, edgeY, queryX, queryY, queryLB, queryRB, false);
vector<int> resB = calc(n, edgeX, edgeY, queryX, queryY, queryLB, queryRB, true);
vector<int> merge(size(resA));
for (int i = 0; i < size(resA); i++) {
if (resA[i] != -1) {
// assert(resB[i] == -1);
merge[i] = resA[i];
}
else {
assert(resB[i] != -1);
merge[i] = resB[i];
}
}
return merge;
}
Compilation message
werewolf.cpp: In function 'std::vector<int> calc(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, bool)':
werewolf.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int i = 0; i < sz(edgeX); i++) {
| ^
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from werewolf.cpp:2:
werewolf.cpp:71:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
71 | assert(sz(path) == n);
| ^
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:147:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for (int i = 0; i < size(resA); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
345 ms |
93576 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
