#include "werewolf.h"
#include <iostream>
using namespace std;
const int nmax=200005;
int i,j,n,nr,m;
int tt[nmax],rg[nmax],T[nmax];
int finds(int x)
{
while(x!=tt[x])
x=tt[x];
return x;
}
void unite(int A,int B)
{
if(rg[A]<rg[B]) swap(A,B);
tt[B]=A;rg[A]+=rg[B];
}
vector<int> v[nmax];
struct arbore
{
int t[20][nmax],l[nmax],r[nmax],rep[nmax];
vector<int> ad[nmax];
void dfs(int x)
{
++nr;l[x]=nr;rep[nr]=x;
for(int i=0;i<ad[x].size();i++)
dfs(ad[x][i]);
r[x]=nr;
}
void solve()
{
for(i=1;i<=18;i++)
for(j=0;j<n;j++)
t[i][j]=t[i-1][t[i-1][j]];
int rad=0;
for(i=0;i<n;i++)
if(t[0][i]!=-1) ad[t[0][i]].push_back(i);
else rad=i;
nr=0;
dfs(rad);
}
int cb(int x,int lim,int par)
{
for(int p=18;p>=0;p--)
if(t[p][x]!=-1&&((t[p][x]>=lim&&par==0)||(t[p][x]<=lim&&par==1)))
x=t[p][x];
return x;
}
}mic,mare;
int aib[nmax],pica[nmax];
inline int lbit(int x)
{
return ((x^(x-1))&x);
}
void update(int poz,int val)
{
for(int idx=poz;idx<=n;idx+=lbit(idx))
aib[idx]+=val;
}
int compute(int poz)
{
int ret=0;
for(int idx=poz;idx>0;idx-=lbit(idx))
ret+=aib[idx];
return ret;
}
struct ev
{
int ll,rr,wh,sgn;
};
vector<ev> qr[nmax];
int cat[nmax];
void sweep()
{
for(i=1;i<=n;i++)
{
pica[mic.rep[i]]=i;
}
for(i=1;i<=n;i++)
{
update(pica[mare.rep[i]],1);
for(j=0;j<qr[i].size();j++)
cat[qr[i][j].wh]+=(compute(qr[i][j].rr)-compute(qr[i][j].ll-1))*qr[i][j].sgn;
}
}
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 Q = S.size();
m=X.size();n=N;
std::vector<int> A(Q);
for(int i=0;i<m;i++)
{
v[X[i]].push_back(Y[i]);
v[Y[i]].push_back(X[i]);
}
for(i=0;i<n;i++)
mic.t[0][i]=mare.t[0][i]=-1;
for(i=0;i<n;i++)
{
tt[i]=i;rg[i]=1;T[i]=i;
for(j=0;j<v[i].size();j++)
if(v[i][j]<i&&finds(v[i][j])!=finds(i))
{
mic.t[0][T[finds(v[i][j])]]=i;
unite(finds(i),finds(v[i][j]));
}
T[finds(i)]=i;
}
mic.solve();
for(i=n-1;i>=0;i--)
{
tt[i]=i;rg[i]=1;T[i]=i;
for(j=0;j<v[i].size();j++)
if(v[i][j]>i&&finds(v[i][j])!=finds(i))
{
mare.t[0][T[finds(v[i][j])]]=i;
unite(finds(i),finds(v[i][j]));
}
T[finds(i)]=i;
}
mare.solve();
int q=L.size(),ss,ee;
for(i=0;i<q;i++)
{
ss=mare.cb(S[i],L[i],0);ee=mic.cb(E[i],R[i],1);
qr[mare.l[ss]-1].push_back({mic.l[ee],mic.r[ee],i,-1});
qr[mare.r[ss]].push_back({mic.l[ee],mic.r[ee],i,1});
}
sweep();
for(i=0;i<q;i++)
{
if(cat[i]) A[i]=1;
else A[i]=0;
}
return A;
}
Compilation message
werewolf.cpp: In member function 'void arbore::dfs(int)':
werewolf.cpp:26:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ad[x].size();i++)
~^~~~~~~~~~~~~
werewolf.cpp: In function 'void sweep()':
werewolf.cpp:82:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<qr[i].size();j++)
~^~~~~~~~~~~~~
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:102:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<v[i].size();j++)
~^~~~~~~~~~~~
werewolf.cpp:114:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<v[i].size();j++)
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
19448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
19448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1062 ms |
101316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
19448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
