#include <bits/stdc++.h>
#define vi vector<int>
#define gi greater<int>
#define gr greater
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e9
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 2e5+5
using namespace std;
const int MOD = 1e9+7;
const int nax = 2e5+5;
typedef complex<int> Point;
//#define X real()
//#define Y imag()
#include "werewolf.h"
vi fin, adj[nax];
ii st[nax*4];
int ind[nax];
void dfs(int u, int p){
fin.pb(u);
for(auto x : adj[u]){
if(x == p) continue;
dfs(x,u);
}
}
void build(int v,int l, int r){
if(l ==r) {
st[v].fi = st[v].se = fin[l];
return;
}
int md = (l+r)/2;
build(v*2, l, md);
build(v*2+1, md+1, r);
st[v].fi = max(st[v*2].fi, st[v*2+1].fi);
st[v].se = min(st[v*2].se, st[v*2+1].se);
}
int query(int v, int l, int r, int i, int j, int ind){
if(i > j) swap(i,j);
if(r < i ||l > j) {
if(ind) return INF;
else return 0;
}
if(i <= l && r <= j){
if(ind) return st[v].se;
else return st[v].fi;
}
int md = (l+r)/2;
if(!ind) return max(query(v*2,l,md,i,j,ind), query(v*2+1, md+1, r, i, j, ind));
else return min(query(v*2,l,md,i,j,ind), query(v*2+1, md+1, r, i, j, ind));
}
vi check_validity(int n, vi x, vi y, vi s, vi e, vi low,vi high) {
int m = x.size();
for (int i = 0; i < m; ++i)
{
adj[x[i]].pb(y[i]);
adj[y[i]].pb(x[i]);
}
for (int i = 0; i < n; ++i)
{
if(adj[i].size() == 1){
dfs(i,i);
break;
}
}
build(1,0,n-1);
for (int i = 0; i < n; ++i)
{
ind[fin[i]] = i;
}
int q = s.size();
vi a(q);
for (int i = 0; i < q; ++i) {
int l = min(ind[e[i]],ind[s[i]]), r = max(ind[e[i]],ind[s[i]])+1;
while(l < r){
int md = (l+r)/2;
int mn = query(1,0,n-1, ind[s[i]], md, 1), mx = query(1,0,n-1, md, ind[e[i]], 0);
if(mn < low[i] && mx > high[i]){
a[i] = 0;
break;
} else if(mn < low[i]){
if(s[i] < e[i]) r = md;
else l = md+1;
} else if(mx > high[i]) {
if(s[i] < e[i]) l = md+1;
else r = md;
} else{
if(mx >= low[i] || mn <= high[i]) a[i] = 1;
else a[i] = 0;
break;
}
}
}
return a;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
312 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
312 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
402 ms |
36788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
312 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
