#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
#define OVL(v,s) for(auto x:v) cout<<x<<s;cout<<endl;
#define ll long long
#define pb push_back
const int MAXN=2e5;
int tree[4*MAXN][2];
vector<int> euler;
vector<vector<int>> v(MAXN);
const int INF=1e9;
void build(int node,int l,int r){
if(l==r){
tree[node][0]=euler[l];
tree[node][1]=euler[l];
return;
}
int mid=(l+r)/2;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
tree[node][0]=min(tree[node<<1][0],tree[node<<1|1][0]);
tree[node][1]=max(tree[node<<1][1],tree[node<<1|1][1]);
}
int query1(int node,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return tree[node][0];
int ans=INF;
int mid=(l+r)/2;
if(ql<=mid) ans=min(ans,query1(node<<1,l,mid,ql,qr));
if(qr>mid) ans=min(ans,query1(node<<1|1,mid+1,r,ql,qr));
return ans;
}
int query2(int node,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return tree[node][1];
int ans=0;
int mid=(l+r)/2;
if(ql<=mid) ans=max(ans,query2(node<<1,l,mid,ql,qr));
if(qr>mid) ans=max(ans,query2(node<<1|1,mid+1,r,ql,qr));
return ans;
}
void dfs(int node,int par){
euler.push_back(node);
for(auto x:v[node]) {
if(x==par) continue;
dfs(x,node);
}
}
vector<int> check_validity(int n, vector<int> a, vector<int> b,
vector<int> ql, vector<int> qr,
vector<int> L, vector<int> R) {
int q = ql.size();
for(int i=0;i<a.size();i++){
v[a[i]].pb(b[i]);
v[b[i]].pb(a[i]);
}
map<int,int> mp;
for(int i=0;i<n;i++){
if(v[i].size()==1){
dfs(i,i);
break;
}
}
for(int i=0;i<n;i++){
mp[euler[i]]=i;
}
build(1,0,n-1);
vector<int> anns(q,0);
for(int j=0;j<q;j++){
int qql=ql[j];
int qqr=qr[j];
if(mp[qql]<mp[qqr]) {
int l=mp[qql];
int r=mp[qqr]+1;
int mid;
int ans=0;
while(l<=r){
mid=(l+r)/2;
if(query1(1,0,n-1,mp[qql],mid)>=L[j]){
ans=mid;
l=mid+1;
}else r=mid-1;
}
anns[j]=(query1(1,0,n-1,mp[qql],ans)>=L[j]&&query2(1,0,n-1,ans,mp[qqr])<=R[j]);
}else{
int l=mp[qqr];
int r=mp[qql];
int mid;
int ans=0;
while(l<=r){
mid=(l+r)/2;
if(query1(1,0,n-1,mid,mp[qql])>=L[j]) {
ans=mid;
l=mid+1;
}else r=mid-1;
}
anns[j]=(query1(1,0,n-1,ans,mp[qql])>=L[j]&&query2(1,0,n-1,mp[qqr],ans)<=R[j]);
}
}
return anns;
}
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:52:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i=0;i<a.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
300 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
300 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1202 ms |
45148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
300 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
