//#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9+7;
struct node{
int maxi=0;
int mini=INF;
};
node none={0, INF};
struct segtree{
vector<node> tree;
segtree(int n){
tree.assign(n*4, none);
}
node merge(node a, node b){
a.maxi = max(a.maxi, b.maxi);
a.mini = min(a.mini, b.mini);
return a;
}
node update(int l, int r, int v, int x, int val){
if(x<l || r<=x) return tree[v];
if(l+1==r){
return tree[v]={val, val};
}
int m=l+(r-l)/2;
return tree[v] = merge(update(l, m, v*2+1, x, val), update(m, r, v*2+2, x, val));
}
node query(int l, int r, int v, int ql, int qr){
if(qr<=l || r<=ql) return none;
if(ql<=l && r<=qr){
return tree[v];
}
int m=l+(r-l)/2;
return merge(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
}
};
bool line_query(int n, segtree& seg, int a, int b, int left, int right){
int l=a; int r=b;
int ans=-1;
while(l<=r){
int m=l+(r-l)/2;
if(left <= seg.query(0, n, 0, a, m+1).mini){
ans = m;
l = m+1;
}
else{
r=m-1;
}
}
int lastr=ans;
l=a; r=b;
ans=n;
while(l<=r){
int m=l+(r-l)/2;
if(seg.query(0, n, 0, m, b).maxi <= right){
ans = m;
r = m-1;
}
else{
l = l+1;
}
}
int lastl=ans;
return lastl <= lastr;
}
vector<int> solve_line(int n, vector<vector<int> >& adi, vector<int>& s, vector<int>& e,
vector<int>& l, vector<int>& r){
//find line
vector<int> line;
int start=0;
for(int v=0; v<n; v++){
if(adi[v].size()==1){
start=v;
}
}
line.push_back(start);
int v=adi[start][0]; int p=start;
for(int i=0; i<n-1; i++){
line.push_back(v);
for(auto u: adi[v]){
if(u!=p){
v=u;
break;
}
}
p=v;
}
vector<int> ind(n);
for(int i=0; i<n; i++){
ind[line[i]]=i;
}
//initialize segtree
segtree seg(n);
for(int i=0; i<n; i++){
seg.update(0, n, 0, i, line[i]);
}
//answer queries
int q=s.size();
vector<int> ans(q);
for(int i=0; i<q; i++){
int a=ind[s[i]]; int b=ind[e[i]];
if(b<a){
swap(l[i], r[i]);
swap(a, b);
}
ans[i] = line_query(n, seg, a, b, l[i], r[i]);
}
return ans;
}
vector<int> check_validity(int n, vector<int> x, vector<int> y,
vector<int> s, vector<int> e,
vector<int> l, vector<int> r) {
int m=x.size();
vector<vector<int> > adi(n);
for(int i=0; i<m; i++){
adi[x[i]].push_back(y[i]);
adi[y[i]].push_back(x[i]);
}
return solve_line(n, adi, s, e, l, r);
}
| # |
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 |
Incorrect |
267 ms |
37852 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 |
- |
