#include "werewolf.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back()
#define ss second
#define ff first
#define mt make_tuple
#define pof pop_front()
#define fbo find_by_order
#define ook order_of_key
#define lb lower_bound
#define ub upper_bound
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
int cnt[200001], mntr[600001], mxtr[600001], pos[200001];
vector <int> arr, edg[200001], ans;
void build(int node, int l, int r)
{
if ( l == r )
{
mxtr[node] = arr[l - 1];
mntr[node] = arr[l - 1];
return;
}
int mid = (l + r) / 2;
build(node * 2, l, mid);
build(node * 2 + 1, mid + 1, r);
mxtr[node] = max(mxtr[node * 2], mxtr[node * 2 + 1]);
mntr[node] = min(mntr[node * 2], mntr[node * 2 + 1]);
}
int mx(int node, int l, int r, int L, int R)
{
if ( l > R || r < L )
return 0;
if ( l >= L && r <= R )
return mxtr[node];
int mid = (l + r) / 2;
return max(mx(node * 2, l, mid, L, R), mx(node * 2 + 1, mid + 1, r, L, R));
}
int mn(int node, int l, int r, int L, int R)
{
if ( l > R || r < L )
return 1e9;
if ( l >= L && r <= R )
return mntr[node];
int mid = (l + r) / 2;
return min(mn(node * 2, l, mid, L, R), mn(node * 2 + 1, mid + 1, r, L, R));
}
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++)
{
edg[X[i]].pub(Y[i]);
edg[Y[i]].pub(X[i]);
cnt[X[i]]++;
cnt[Y[i]]++;
}
for (int i = 0; i < N; i++)
{
if ( cnt[i] == 1 )
{
queue<pii> q;
q.push(mp(i, -1));
while (!q.empty())
{
int u = q.front().ff;
int par = q.front().ss;
q.pop();
arr.pub(u);
pos[u] = arr.size();
for (auto v : edg[u])
if ( v != par )
q.push(mp(v, u));
}
break;
}
}
build(1, 1, N);
for (int i = 0; i < S.size(); i++)
{
if ( pos[S[i]] < pos[E[i]] )
{
int l = pos[S[i]], r = pos[E[i]], Ls = -1, Le = -1;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if ( mn(1, 1, N, pos[S[i]], mid) > L[i] )
l = mid;
else
r = mid;
}
if ( mn(1, 1, N, pos[S[i]], r) > L[i] )
Ls = r;
else if ( mn(1, 1, N, pos[S[i]], l) > L[i] )
Ls = l;
l = pos[S[i]], r = pos[E[i]];
while (l + 1 < r)
{
int mid = (l + r) / 2;
if ( mx(1, 1, N, mid, pos[E[i]]) <= R[i] + 1 )
r = mid;
else
l = mid;
}
if ( mx(1, 1, N, l, pos[E[i]]) <= R[i] + 1 )
Le = l;
else if ( mx(1, 1, N, r, pos[E[i]]) <= R[i] + 1 )
Le = r;
if ( Ls >= Le && Ls != -1 && Le != -1 )
ans.pub(1);
else
ans.pub(0);
} else {
int l = pos[S[i]], r = pos[E[i]], Ls = -1, Le = -1;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if ( mn(1, 1, N, mid, pos[S[i]]) > L[i] )
r = mid;
else
l = mid;
}
if ( mn(1, 1, N, pos[S[i]], l) > L[i] )
Ls = r;
else if ( mn(1, 1, N, pos[S[i]], r) > L[i] )
Ls = l;
l = pos[S[i]], r = pos[E[i]];
while (l + 1 < r)
{
int mid = (l + r) / 2;
if ( mx(1, 1, N, pos[E[i]], mid) <= R[i] + 1 )
l = mid;
else
r = mid;
}
if ( mx(1, 1, N, pos[E[i]], r) <= R[i] + 1 )
Le = r;
else if ( mx(1, 1, N, pos[E[i]], l) <= R[i] + 1 )
Le = r;
if ( Ls <= Le && Ls != -1 && Le != -1 )
ans.pub(1);
else
ans.pub(0);
}
}
return ans;
}
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:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < X.size(); i++)
~~^~~~~~~~~~
werewolf.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < S.size(); i++)
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1704 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1704 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1534 ms |
31044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1704 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
