#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
vector<int> lg;
struct Sparse1 {
int n;
int LOG;
vector<vector<int>> table;
Sparse1(vector<int>& a) {
n = a.size();
LOG = (int)(log2(n)) + 1;
table = vector<vector<int>>(n, vector<int>(LOG));
for(int i = 0; i < n; ++i) {
table[i][0] = a[i];
}
for(int j = 1; j < LOG; ++j) {
for(int i = 0; i + (1 << j) <= n; ++i) {
table[i][j] = min(table[i][j - 1], table[(1 << (j - 1)) + i][j - 1]);
}
}
}
int get(int low, int high) {
int sz = (high - low + 1);
int l = lg[sz];
return min(table[low][l], table[high - (1 << l) + 1][l]);
}
};
struct Sparse2 {
int n;
int LOG;
vector<vector<int>> table;
Sparse2(vector<int>& a) {
n = a.size();
LOG = (int)(log2(n)) + 1;
table = vector<vector<int>>(n, vector<int>(LOG));
for(int i = 0; i < n; ++i) {
table[i][0] = a[i];
}
for(int j = 1; j < LOG; ++j) {
for(int i = 0; i + (1 << j) <= n; ++i) {
table[i][j] = max(table[i][j - 1], table[(1 << (j - 1)) + i][j - 1]);
}
}
}
int get(int low, int high) {
int sz = (high - low + 1);
int l = lg[sz];
return max(table[low][l], table[high - (1 << l) + 1][l]);
}
};
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) {
lg.resize(n + 1);
for(int i = 2; i <= n; ++i) {
lg[i] = lg[i / 2] + 1;
}
int q = s.size();
vector<int> a(q);
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]);
}
int root = 0;
for(int i = 0; i < n; ++i) {
if(adj.size() == 1) {
root = i;
break;
}
}
// dbg(adj)
// dbg(root)
vector<int> arr;
vector<int> inv(n);
function<void(int, int)> build = [&](int node, int p = -1) {
// dbg(node)
inv[node] = (int)arr.size();
arr.push_back(node);
for(int x : adj[node]) {
if(p == x) continue;
build(x, node);
}
};
build(root, -1);
Sparse1 mn(arr);
Sparse2 mx(arr);
// dbg(inv)
// dbg(arr)
for(int i = 0; i < q; ++i) {
int s_l = inv[s[i]];
int s_r = inv[e[i]];
// dbg(s_l, s_r)
if(s_l <= s_r) {
int low = s_l, high = s_r; // max to human
while(low < high) {
int mid = (low + high + 1) / 2;
if(mn.get(s_l, mid) >= l[i]) {
low = mid;
} else {
high = mid - 1;
}
}
int f = high;
low = s_l, high = s_r; // max to wolf
while(low < high) {
int mid = (low + high) / 2;
if(mx.get(mid, s_r) <= r[i]) {
high = mid;
} else {
low = mid + 1;
}
}
int s = low;
if(f <= s) {
a[i] = 1;
}
}
else {
swap(s_l, s_r);
int low = s_l, high = s_r; // min to human
while(low < high) {
int mid = (low + high) / 2;
if(mn.get(mid, s_r) >= l[i]) {
high = mid;
} else {
low = mid + 1;
}
}
int s = high;
low = s_l, high = s_r; // max to wolf
while(low < high) {
int mid = (low + high + 1) / 2;
if(mx.get(s_l, mid) <= r[i]) {
low = mid;
} else {
high = mid - 1;
}
}
int f = low;
if(s <= f) {
a[i] = 1;
}
}
}
return a;
}
/*
6 5 3
4 3
1 2
3 1
5 4
0 2
4 2 2 2
0 5 2 5
0 5 1 5
*/
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:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 0; i < x.size(); ++i) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
269 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
269 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
525 ms |
77452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
269 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
