#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define F first
#define S second
#define sz(x) (ll)x.size()
#define MID ((l+r)/2)
#define pb push_back
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;
#define dbg4(x,y,z,w) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<" "<<#w<<": "<<w<<endl;
#define INF 1e9
typedef vector <ll> vi;
typedef pair<ll,ll> ii;
typedef vector <ii> vii;
void printVct(vi &v, string s =""){
if (sz(s) > 0) cout<<s<<": ";
for (ll i=0; i<sz(v); i++){
cout<<v[i]<<" ";
}
cout<<endl;
}
void tabb(ll n) {
for (ll i= 0; i<n; i++) cout<<"\t";
}
vector <vi> adj;
ll n,m;
vi arr, inv, vis;
void dfs(ll u){
vis[u] = 1;
arr.pb(u);
for (ll i=0; i<sz(adj[u]); i++){
if (!vis[adj[u][i]]){
dfs(adj[u][i]);
}
}
}
struct node{
ll mini, maxi;
node *L, *R;
void build (ll l = 0, ll r = n-1){
// tabb(tab);
// dbg2(l,r);
if (l == r){
mini = arr[l];
maxi = arr[l];
}
else{
L = new node;
R = new node;
L -> build (l, MID);
R -> build (MID+1, r);
mini =min(L->mini, R->mini);
maxi =max(L->maxi, R->maxi);
}
// tabb(tab);
// dbg2(mini, maxi);
}
ll queryMin(ll tl, ll tr, ll l = 0, ll r = n-1){
if (l >= tl && r <= tr) return mini;
else if (tl > r || tr < l) return INF;
return min(L->queryMin(tl,tr,l,MID), R->queryMin(tl,tr,MID+1,r));
}
ll queryMax(ll tl, ll tr, ll l = 0, ll r = n-1){
//dbg4(tl,tr,l,r);
if (l >= tl && r <= tr) return maxi;
else if (tl > r || tr < l) return -1;
return max(L->queryMax(tl,tr,l,MID), R->queryMax(tl,tr,MID+1,r));
}
};
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R){
m = sz(X),n = N;
vi deg(n, 0);
adj.assign(n, vi());
for (ll i=0;i<m; i++){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
deg[X[i]]++;
deg[Y[i]]++;
}
//find start
ll p = -1;
for (ll i = 0; i<n; i++){
if (deg[i] == 1){
p =i;
break;
}
}
if (p == -1) return vi();
//prepare arrays
arr.clear(), inv.resize(n);
vis.assign(n, 0);
dfs(p);
for (ll i= 0; i<n;i++){
inv[arr[i]] = i;
}
// printVct(arr, "arr");
// printVct(inv,"inv");
//build seg
node root;
root.build();
//solve
vi ans;
ll q = sz(L);
for (ll i=0; i<q; i++){
ll s = S[i], e= E[i], tl = L[i], tr = R[i];
ll idxS = inv[s], idxE = inv[e];
// dbg2(idxS, idxE);
if (idxS < idxE){
// cout<<"INININII"<<endl;
//dbg2(root.queryMin(3, 7), root.queryMax(4, 6));
ll l = idxS, r = idxE, mid;
ll L_idx = idxS;
while (l <= r){
mid = MID;
// dbg3(l,r,mid);
bool ok = (root.queryMin(l, mid) >= tl);
// dbg(root.queryMin(l, mid));
if (ok){
l = mid+1;
L_idx = mid;
}
else{
r = mid-1;
}
}
// dbg(L_idx);
if (root.queryMax(L_idx, idxE) <= tr){
ans.pb(1);
// cout<<"OK"<<endl;
}
else{
ans.pb(0);
// cout<<"NOT OK"<<endl;
}
}
else{
ll l = idxE, r = idxS, mid;
ll R_idx = idxS;
while (l <= r){
mid = MID;
// dbg3(l,r,mid);
bool ok = (root.queryMin(mid, r) >= tl);
// dbg(root.queryMin(mid, r));
if (ok){
r = mid-1;
R_idx = mid;
}
else{
l = mid+1;
}
}
// dbg(R_idx);
// dbg(root.queryMax(idxE, R_idx));
if (root.queryMax(idxE, R_idx) <= tr){
ans.pb(1);
// cout<<"OK"<<endl;
}
else{
ans.pb(0);
// cout<<"NOT OK"<<endl;
}
}
}
// cout<<endl;
// printVct(ans, "ans");
return ans;
}
/*
8 7 1
3 1
1 0
0 6
6 2
2 4
4 5
5 7
3 7 1 7
5 3 1 6
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
Compilation message
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:115:10: warning: 'root.node::R' may be used uninitialized in this function [-Wmaybe-uninitialized]
115 | node root;
| ^~~~
werewolf.cpp:115:10: warning: 'root.node::L' may be used uninitialized in this function [-Wmaybe-uninitialized]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1030 ms |
49488 KB |
Output is correct |
| 2 |
Correct |
1188 ms |
55588 KB |
Output is correct |
| 3 |
Correct |
898 ms |
55572 KB |
Output is correct |
| 4 |
Correct |
868 ms |
55664 KB |
Output is correct |
| 5 |
Correct |
1060 ms |
55552 KB |
Output is correct |
| 6 |
Correct |
953 ms |
55608 KB |
Output is correct |
| 7 |
Correct |
862 ms |
55656 KB |
Output is correct |
| 8 |
Correct |
894 ms |
55660 KB |
Output is correct |
| 9 |
Correct |
382 ms |
55576 KB |
Output is correct |
| 10 |
Correct |
446 ms |
55656 KB |
Output is correct |
| 11 |
Correct |
520 ms |
55580 KB |
Output is correct |
| 12 |
Correct |
492 ms |
55584 KB |
Output is correct |
| 13 |
Correct |
914 ms |
55744 KB |
Output is correct |
| 14 |
Correct |
873 ms |
55740 KB |
Output is correct |
| 15 |
Correct |
872 ms |
55664 KB |
Output is correct |
| 16 |
Correct |
892 ms |
55624 KB |
Output is correct |
| 17 |
Correct |
947 ms |
55584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
