/**
* Author : boatinw99
* Date : 4.5.2019 10.50 - 11.15 , 12.50
*/
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std ;
typedef pair<int,int> pii ;
#define mid (l+r>>1)
#define fi first
#define se second
const int N = 2e5+9 ,inf = 1e9 ,LOG=log2(N)+1 ;
struct Q
{
int st,ed,l,r,idx ;
}query[N];
int L[N*LOG*2],R[N*LOG*2],st[N*LOG*2],idx=1,root[N];
pii edge[N<<1] ;
int n,m,q;
void construct(int l,int r,int m)
{
if(l==r)return ;
L[m]=++idx,R[m]=++idx;
construct(l,mid,L[m]);
construct(mid+1,r,R[m]);
}
int update(int l,int r,int x,int m)
{
if(r<x||l>x)return m;
int nw = ++idx ;
if(l==r)
{
st[nw]++;
return nw ;
}
L[nw]=update(l,mid,x,L[m]),R[nw]=update(mid+1,r,x,R[m]);
st[nw]=st[L[nw]]+st[R[nw]];
return nw ;
}
int getsum(int l,int r,int x,int y,int m1,int m2)
{
if(r<x||l>y)return 0 ;
if(l>=x&&r<=y)return st[m1]-st[m2];
return getsum(l,mid,x,y,L[m1],L[m2])+getsum(mid+1,r,x,y,R[m1],R[m2]);
}
struct tree
{
int up[N][LOG],cst[N][LOG],tin[N],tout[N],times = 0 ; /// cst-> min or max
int rnk[N],p[N],val[N],euler[N],pos[N],idx=0;
vector<int> g[N];
void init()
{
for(int i=1;i<=n;i++)p[i]=val[i]=i ;
}
int find(int u)
{
return u==p[u]?u:p[u]=find(p[u]);
}
bool Union0(int u,int v)
{
u=find(u),v=find(v);
if(u==v)return 0;
int mn = min(val[u],val[v]);
if(rnk[u]>=rnk[v])swap(u,v);
rnk[v]+=rnk[u];
g[val[v]].emplace_back(val[u]);
g[val[u]].emplace_back(val[v]);
val[v]=mn;
p[u]=v;
return 1;
}
bool Union1(int u,int v)
{
u=find(u),v=find(v);
if(u==v)return 0;
int mn = max(val[u],val[v]);
if(rnk[u]>=rnk[v])swap(u,v);
rnk[v]+=rnk[u];
g[val[v]].emplace_back(val[u]);
g[val[u]].emplace_back(val[v]);
val[v]=mn;
p[u]=v;
return 1;
}
void dfs0(int u,int v)
{
up[u][0]=v;
tin[u]=++times;
pos[u]=times;
euler[times]=u;
for(int i=1;i<LOG;i++)
{
up[u][i]=up[up[u][i-1]][i-1];
cst[u][i]=cst[up[u][i-1]][i-1];
}
for(auto it:g[u])if(it!=v)cst[it][0]=u,dfs0(it,u);
tout[u]=times;
}
void dfs1(int u,int v)
{
up[u][0]=v;
tin[u]=++times;
pos[u]=times;
euler[times]=u;
for(int i=1;i<LOG;i++)
{
up[u][i]=up[up[u][i-1]][i-1];
cst[u][i]=cst[up[u][i-1]][i-1];
}
for(auto it:g[u])if(it!=v)cst[it][0]=u,dfs1(it,u);
tout[u]=times;
}
int bliftmin(int u,int val)
{
for(int i=LOG-1;i>=0;i--)if(cst[u][i]>=val)u=up[u][i];
return u;
}
int bliftmax(int u,int val)
{
for(int i=LOG-1;i>=0;i--)if(cst[u][i]<=val)u=up[u][i];
return u ;
}
}t1,t2;
void constructdsu()
{
t1.init();
sort(edge+1,edge+1+m,[&](const pii a,const pii b){
return min(a.fi,a.se)>min(b.fi,b.se);});
for(int i=1;i<=m;i++)t1.Union0(edge[i].fi,edge[i].se);
t1.dfs0(1,1);
t2.init();
sort(edge+1,edge+1+m,[&](const pii a,const pii b){
return max(a.fi,a.se)<max(b.fi,b.se);});
for(int i=1;i<=m;i++)t2.Union1(edge[i].fi,edge[i].se);
t2.up[n][0]=n;
t2.cst[n][0]=inf;
t2.dfs1(n,n);
}
vector<int> check_validity(int SZ,vector<int> X,vector<int> Y,
vector<int> S,vector<int> E,
vector<int> le,vector<int> ri)
{
n=SZ;
m=X.size();
q=S.size();
vector<int> ans(q);
for(int i=1;i<=m;i++)edge[i]={X[i-1]+1,Y[i-1]+1};
for(int i=1;i<=q;i++)query[i]={S[i-1]+1,E[i-1]+1,le[i-1]+1,ri[i-1]+1,i};
constructdsu();
root[0]=1;
construct(1,n,1);
for(int i=1;i<=n;i++)root[i]=update(1,n,t2.pos[t1.euler[i]],root[i-1]);
sort(query+1,query+1+q,[&](const Q a,const Q b){
return a.r<b.r;});
for(int i=1;i<=q;i++)
{
int u = t1.bliftmin(query[i].st,query[i].l);
int v = t2.bliftmax(query[i].ed,query[i].r);
ans[query[i].idx-1]=(getsum(1,n,t2.tin[v],t2.tout[v],
root[t1.tout[u]],root[t1.tin[u]-1])>0);
}
return ans ;
}
Compilation message
werewolf.cpp: In function 'void construct(int, int, int)':
werewolf.cpp:10:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define mid (l+r>>1)
~^~
werewolf.cpp:25:17: note: in expansion of macro 'mid'
construct(l,mid,L[m]);
^~~
werewolf.cpp:10:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define mid (l+r>>1)
~^~
werewolf.cpp:26:15: note: in expansion of macro 'mid'
construct(mid+1,r,R[m]);
^~~
werewolf.cpp: In function 'int update(int, int, int, int)':
werewolf.cpp:10:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define mid (l+r>>1)
~^~
werewolf.cpp:37:20: note: in expansion of macro 'mid'
L[nw]=update(l,mid,x,L[m]),R[nw]=update(mid+1,r,x,R[m]);
^~~
werewolf.cpp:10:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define mid (l+r>>1)
~^~
werewolf.cpp:37:45: note: in expansion of macro 'mid'
L[nw]=update(l,mid,x,L[m]),R[nw]=update(mid+1,r,x,R[m]);
^~~
werewolf.cpp: In function 'int getsum(int, int, int, int, int, int)':
werewolf.cpp:10:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define mid (l+r>>1)
~^~
werewolf.cpp:45:21: note: in expansion of macro 'mid'
return getsum(l,mid,x,y,L[m1],L[m2])+getsum(mid+1,r,x,y,R[m1],R[m2]);
^~~
werewolf.cpp:10:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
#define mid (l+r>>1)
~^~
werewolf.cpp:45:49: note: in expansion of macro 'mid'
return getsum(l,mid,x,y,L[m1],L[m2])+getsum(mid+1,r,x,y,R[m1],R[m2]);
^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
9856 KB |
Output is correct |
2 |
Correct |
13 ms |
10012 KB |
Output is correct |
3 |
Correct |
10 ms |
9856 KB |
Output is correct |
4 |
Correct |
11 ms |
9900 KB |
Output is correct |
5 |
Correct |
11 ms |
9984 KB |
Output is correct |
6 |
Correct |
10 ms |
9856 KB |
Output is correct |
7 |
Correct |
13 ms |
9984 KB |
Output is correct |
8 |
Correct |
10 ms |
9984 KB |
Output is correct |
9 |
Correct |
10 ms |
9984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
9856 KB |
Output is correct |
2 |
Correct |
13 ms |
10012 KB |
Output is correct |
3 |
Correct |
10 ms |
9856 KB |
Output is correct |
4 |
Correct |
11 ms |
9900 KB |
Output is correct |
5 |
Correct |
11 ms |
9984 KB |
Output is correct |
6 |
Correct |
10 ms |
9856 KB |
Output is correct |
7 |
Correct |
13 ms |
9984 KB |
Output is correct |
8 |
Correct |
10 ms |
9984 KB |
Output is correct |
9 |
Correct |
10 ms |
9984 KB |
Output is correct |
10 |
Correct |
19 ms |
11904 KB |
Output is correct |
11 |
Correct |
23 ms |
11904 KB |
Output is correct |
12 |
Correct |
22 ms |
11904 KB |
Output is correct |
13 |
Correct |
22 ms |
12032 KB |
Output is correct |
14 |
Correct |
22 ms |
12024 KB |
Output is correct |
15 |
Correct |
19 ms |
12128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1299 ms |
156748 KB |
Output is correct |
2 |
Correct |
1022 ms |
159552 KB |
Output is correct |
3 |
Correct |
903 ms |
158060 KB |
Output is correct |
4 |
Correct |
932 ms |
157288 KB |
Output is correct |
5 |
Correct |
917 ms |
157276 KB |
Output is correct |
6 |
Correct |
1398 ms |
157152 KB |
Output is correct |
7 |
Correct |
1243 ms |
157204 KB |
Output is correct |
8 |
Correct |
1064 ms |
159736 KB |
Output is correct |
9 |
Correct |
766 ms |
158072 KB |
Output is correct |
10 |
Correct |
615 ms |
157368 KB |
Output is correct |
11 |
Correct |
658 ms |
157128 KB |
Output is correct |
12 |
Correct |
798 ms |
157304 KB |
Output is correct |
13 |
Correct |
1083 ms |
160556 KB |
Output is correct |
14 |
Correct |
1022 ms |
160888 KB |
Output is correct |
15 |
Correct |
1086 ms |
160888 KB |
Output is correct |
16 |
Correct |
1234 ms |
160888 KB |
Output is correct |
17 |
Correct |
1096 ms |
157408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
9856 KB |
Output is correct |
2 |
Correct |
13 ms |
10012 KB |
Output is correct |
3 |
Correct |
10 ms |
9856 KB |
Output is correct |
4 |
Correct |
11 ms |
9900 KB |
Output is correct |
5 |
Correct |
11 ms |
9984 KB |
Output is correct |
6 |
Correct |
10 ms |
9856 KB |
Output is correct |
7 |
Correct |
13 ms |
9984 KB |
Output is correct |
8 |
Correct |
10 ms |
9984 KB |
Output is correct |
9 |
Correct |
10 ms |
9984 KB |
Output is correct |
10 |
Correct |
19 ms |
11904 KB |
Output is correct |
11 |
Correct |
23 ms |
11904 KB |
Output is correct |
12 |
Correct |
22 ms |
11904 KB |
Output is correct |
13 |
Correct |
22 ms |
12032 KB |
Output is correct |
14 |
Correct |
22 ms |
12024 KB |
Output is correct |
15 |
Correct |
19 ms |
12128 KB |
Output is correct |
16 |
Correct |
1299 ms |
156748 KB |
Output is correct |
17 |
Correct |
1022 ms |
159552 KB |
Output is correct |
18 |
Correct |
903 ms |
158060 KB |
Output is correct |
19 |
Correct |
932 ms |
157288 KB |
Output is correct |
20 |
Correct |
917 ms |
157276 KB |
Output is correct |
21 |
Correct |
1398 ms |
157152 KB |
Output is correct |
22 |
Correct |
1243 ms |
157204 KB |
Output is correct |
23 |
Correct |
1064 ms |
159736 KB |
Output is correct |
24 |
Correct |
766 ms |
158072 KB |
Output is correct |
25 |
Correct |
615 ms |
157368 KB |
Output is correct |
26 |
Correct |
658 ms |
157128 KB |
Output is correct |
27 |
Correct |
798 ms |
157304 KB |
Output is correct |
28 |
Correct |
1083 ms |
160556 KB |
Output is correct |
29 |
Correct |
1022 ms |
160888 KB |
Output is correct |
30 |
Correct |
1086 ms |
160888 KB |
Output is correct |
31 |
Correct |
1234 ms |
160888 KB |
Output is correct |
32 |
Correct |
1096 ms |
157408 KB |
Output is correct |
33 |
Correct |
1706 ms |
158388 KB |
Output is correct |
34 |
Correct |
378 ms |
35380 KB |
Output is correct |
35 |
Correct |
1972 ms |
159992 KB |
Output is correct |
36 |
Correct |
1675 ms |
157772 KB |
Output is correct |
37 |
Correct |
1748 ms |
159480 KB |
Output is correct |
38 |
Correct |
1849 ms |
158312 KB |
Output is correct |
39 |
Correct |
1283 ms |
164404 KB |
Output is correct |
40 |
Correct |
1334 ms |
163448 KB |
Output is correct |
41 |
Correct |
1516 ms |
159220 KB |
Output is correct |
42 |
Correct |
1215 ms |
157944 KB |
Output is correct |
43 |
Correct |
1941 ms |
162908 KB |
Output is correct |
44 |
Correct |
1490 ms |
159164 KB |
Output is correct |
45 |
Correct |
1160 ms |
164640 KB |
Output is correct |
46 |
Correct |
1275 ms |
164344 KB |
Output is correct |
47 |
Correct |
1278 ms |
160956 KB |
Output is correct |
48 |
Correct |
1268 ms |
161016 KB |
Output is correct |
49 |
Correct |
1278 ms |
160988 KB |
Output is correct |
50 |
Correct |
1222 ms |
161016 KB |
Output is correct |
51 |
Correct |
1401 ms |
163656 KB |
Output is correct |
52 |
Correct |
1479 ms |
163776 KB |
Output is correct |