#include "werewolf.h"
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define F first
#define S second
using namespace std;
typedef int ll;
typedef pair<ll,ll>pll;
ll n,k,p[400009],nn,is;
ll dp1[400009][20],dp2[400009][20];
ll h1[400009],h2[400009];
ll f1[400009],f2[400009];
vector<pll>op;
vector<vector<ll> >v;
vector<ll>ans;
ll gp(ll z)
{
if(p[z]==z)
return z;
return p[z]=gp(p[z]);
}
void mrg(ll x,ll y)
{
x=gp(x),y=gp(y);
if(x==y)
return;
nn++;
p[x]=p[y]=p[nn]=nn;
v[nn].push_back(x);
v[nn].push_back(y);
if(is==1)
f1[nn]=min(f1[x],f1[y]);
else
f2[nn]=max(f2[x],f2[y]);
}
bool cmp1(const pll&x,const pll&y)
{
return min(x.F,x.S)>min(y.F,y.S);
}
bool cmp2(const pll&x,const pll&y)
{
return max(x.F,x.S)<max(y.F,y.S);
}
void dfs(ll d,ll p)
{
if(is==1)
dp1[d][0]=p,h1[d]=h1[p]+1;
else
dp2[d][0]=p,h2[d]=h2[p]+1;
for(auto z:v[d])
if(z!=p)
dfs(z,d);
}
ll lca1(ll x,ll y)
{
if(h1[x]<h1[y])
swap(x,y);
ll j=h1[x]-h1[y];
for(ll i=0; i<=k; i++)
if((1<<i)&j)
x=dp1[x][i];
for(ll i=k; i>=0; i--)
if(dp1[x][i]!=dp1[y][i])
x=dp1[x][i],y=dp1[y][i];
if(x==y)
return x;
return dp1[x][0];
}
ll lca2(ll x,ll y)
{
if(h2[x]<h2[y])
swap(x,y);
ll j=h2[x]-h2[y];
for(ll i=0; i<=k; i++)
if((1<<i)&j)
x=dp2[x][i];
for(ll i=k; i>=0; i--)
if(dp2[x][i]!=dp2[y][i])
x=dp2[x][i],y=dp2[y][i];
if(x==y)
return x;
return dp1[x][0];
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> st, vector<int> en,
vector<int> L, vector<int> R)
{
n=N;
for(ll i=0; i<X.size(); i++)
op.push_back({X[i],Y[i]});
for(ll i=0; i<n; i++)
p[i]=f1[i]=i;
sort(all(op),cmp1),nn=n-1,is=1;
v.resize(2*n);
for(auto z:op)
mrg(z.F,z.S);
dfs(nn,nn);
for(ll i=0; i<n; i++)
p[i]=f2[i]=i;
sort(all(op),cmp2),nn=n-1,is=2;
v.clear(),v.resize(2*n);
for(auto z:op)
mrg(z.F,z.S);
dfs(nn,nn);
k=log2(nn)+1;
for(ll j=1; j<=k; j++)
for(ll i=0; i<=nn; i++)
{
dp1[i][j]=dp1[ dp1[i][j-1] ][j-1];
dp2[i][j]=dp2[ dp2[i][j-1] ][j-1];
}
ans.resize(L.size());
for(ll i=0; i<L.size(); i++)
{
ll x=st[i],y=en[i];
if(f1[lca1(x,y)]>=L[i])
ans[i]=1;
if(f2[lca2(x,y)]<=R[i])
ans[i]=1;
}
return ans;
}
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:89:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(ll i=0; i<X.size(); i++)
| ~^~~~~~~~~
werewolf.cpp:114:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(ll i=0; i<L.size(); i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
945 ms |
102428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
