oj.uz

Submission #109050

# Submission time Handle Problem Language Result Execution time Memory
109050 2019-05-04T06:35:08 Z boatinw99 Werewolf (IOI18_werewolf) C++11
100 / 100
 1972 ms 164640 KB 
/**
 *      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]);
                                                 ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory 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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory 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

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory 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

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory 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