#include <bits/stdc++.h>
#define pb push_back
#include "werewolf.h"
//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif
constexpr static int MXN = 2e5;
constexpr static int MXST = MXN<<1;
constexpr static int INF = 1e6;
using namespace std;
struct SegTree
{
int def;
function<int(int, int)> merge;
int n;
int v[MXN];
void build(int n, int* a, function<int(int, int)> merge, int def)
{
this->n = n;
this->merge = merge;
this->def = def;
for (int i = n; i < 2*n; i++) v[i] = a[i-n];
for (int i = n-1; i > 0; i--) v[i] = merge(v[i<<1], v[(i<<1)|1]);
}
int get(int l, int r)
{
int res = def;
for (l+=n,r+=n;r>l;r>>=1,l>>=1)
{
if (l&1) res = merge(res, v[l++]);
if (r&1) res = merge(res, v[--r]);
}
return res;
}
};
int v[MXN];
int p[MXN];
vector<int> g[MXN];
void find_p(int node, int pr, int current)
{
p[node] = current;
for (int c : g[node])
if (c != pr)
find_p(c, node, current+1);
}
SegTree mnst, mxst;
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> L, vector<int> R) {
for (int i = 0; i < x.size(); i++)
{
g[x[i]].pb(y[i]);
g[y[i]].pb(x[i]);
}
for (int i = 0; i < n; i++)
{
if (g[i].size() == 1)
{
find_p(i, -1, 0);
break;
}
}
for (int i = 0; i < n; i++)
{
v[p[i]] = i;
}
auto mnop = [] (int a, int b) -> int { return min(a, b); };
auto mxop = [] (int a, int b) -> int { return max(a, b); };
mnst.build(n, v, mnop, INF);
mxst.build(n, v, mxop, -1);
vector<int> res;
for (int i = 0; i < s.size(); i++)
{
if (s[i] < L[i] || e[i] > R[i])
{
res.pb(0);
continue;
}
if (p[e[i]] > p[s[i]])
{
int l = -1, r = n+1;
while (r - l > 1)
{
int m = l+r>>1;
if (mnst.get(p[s[i]], m) < L[i])
r = m;
else
l = m;
}
debug(mnst.get(1, 2));
debug(0, l, r);
int ll = l;
l = -1, r = n+1;
while (r - l > 1)
{
int m = l+r>>1;
if (mxst.get(m, p[e[i]]) > R[i])
l = m;
else
r = m;
}
debug(1, l, r);
debug(s[i], e[i], ll, r);
res.pb(ll > r ? 1 : 0);
}
else
{
int l = -1, r = n+1;
while (r - l > 1)
{
int m = l+r>>1;
if (mxst.get(p[e[i]], m) > R[i])
r = m;
else
l = m;
}
debug(2, l, r);
debug(p[e[i]], l, mxst.get(p[e[i]], l));
int ll = l;
l = -1, r = n+1;
while (r - l > 1)
{
int m = l+r>>1;
if (mnst.get(m, p[s[i]]) < L[i])
l = m;
else
r = m;
}
debug(3, l, r);
debug(s[i], e[i], ll, r);
res.pb(ll > r ? 1 : 0);
}
}
return res;
}
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:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int i = 0; i < x.size(); i++)
| ~~^~~~~~~~~~
werewolf.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 0; i < s.size(); i++)
| ~~^~~~~~~~~~
werewolf.cpp:94:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | int m = l+r>>1;
| ~^~
werewolf.cpp:106:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
106 | int m = l+r>>1;
| ~^~
werewolf.cpp:121:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
121 | int m = l+r>>1;
| ~^~
werewolf.cpp:133:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
133 | int m = l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
252 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
252 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
182 ms |
67072 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
252 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
