#include <bits/stdc++.h>
#include "werewolf.h"
#define pb push_back
using namespace std;
const int N=2e5+1,lg=20,inf=1e9;
vector<int> adj[N];
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();
for(int i=0;i<M;i++){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
vector<vector<int>> sp(lg,vector<int>(N,-1)),mn(lg,vector<int>(N,inf)),mx(lg,vector<int>(N,-inf));
vector<int> lvl(N),in(N),out(N);
int time=0;
function<void(int,int,int)> dfs=[&](int a , int p ,int l){
sp[0][a]=p,mn[0][a]=mx[0][a]=a;
in[a]=++time,lvl[a]=l;
for(int i=1;i<lg;i++)
if(sp[i-1][a]!=-1)
sp[i][a]=sp[i-1][sp[i-1][a]],mn[i][a]=min(mn[i-1][a],mn[i-1][sp[i-1][a]]),mx[i][a]=max(mx[i-1][a],mx[i-1][sp[i-1][a]]);
for(int x : adj[a])
if(x!=p)
dfs(x,a,l+1);
out[a]=++time;
return ;
};
function<bool(int,int)> is_ancestor=[&](int p ,int a){
return (in[p]<=in[a]&&out[a]<=out[p]);
};
function<int(int,int)> lca=[&](int a, int b){
if(is_ancestor(a,b)) return a;
if(is_ancestor(b,a)) return b;
for(int i=lg-1;i>-1;i--)
if(sp[i][a]!=-1&&!is_ancestor(sp[i][a],b))
a=sp[i][a];
return sp[0][a];
};
function<int(int,int)> query=[&](int a , int lvl){
int answer=inf ;
for(int i=0;i<lg;i++)
if((1<<i)&lvl){
answer=min(answer,mn[i][a]);
a=sp[i][a];
}
return answer;
};
function<int(int,int)> querymx=[&](int a , int lvl){
int answer=-inf ;
for(int i=0;i<lg;i++)
if((1<<i)&lvl){
answer=max(answer,mn[i][a]);
a=sp[i][a];
}
return answer;
};
dfs(1,-1,0);
vector<int> result ;
for(int i=0;i<E.size();i++){
int s=S[i],e=E[i],l=L[i],r=R[i];
int lc=lca(s,e);
if(query(s,lvl[s]-lvl[lc])<l){
int fs=s;
for(int i=lg-1;i>-1;i--)
if(sp[i][fs]!=-1&&is_ancestor(lc,sp[i][fs])&&mn[i][fs]>=l)
fs=sp[i][fs];
int other= querymx(e,lvl[e]-lvl[lc]);
if(fs!=lc)
other=max(other,querymx(sp[0][fs],lvl[sp[0][fs]]-lvl[lc]));
if(l<=fs&&fs<=r&&other<=r)
result.pb(1);
else{
int fe=e;
for(int i=lg-1;i>-1;--i)
if(sp[i][fe]!=-1&&is_ancestor(lc,sp[i][fe])&&mx[i][fe]<=r)
fe=sp[i][fe];
int other=query(s,lvl[s]-lvl[lc]);
if(fe!=lc)
other=min(other,query(sp[0][fe],lvl[sp[0][fe]]-lvl[lc]));
if(l<=fe&&fe<=r&&other>=l)
result.pb(1);
else
result.pb(0);
}
}
}
return result;
}
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:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i=0;i<E.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
849 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
849 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
950 ms |
87452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
849 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
