oj.uz

Submission #359343

# Submission time Handle Problem Language Result Execution time Memory
359343 2021-01-26T22:31:16 Z Rafi22 Werewolf (IOI18_werewolf) C++14
100 / 100
 981 ms 181356 KB 
#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
const int N=600007,M=600007,Q=600007;
vector<int> G[N];
vector<int> G1[N];
vector<int> DG[N+M];
int dsu[N];
vector<pair<int,int>>poc[N];
vector<pair<int,int>>kon[N];
int q[Q][2];
pair<int,int>seg[Q][2];

int Find(int v)
{
    if(v==dsu[v]) return v;
    return dsu[v]=Find(dsu[v]);
}
int it;
void Union(int u,int v)
{
   u=Find(u),v=Find(v);
   it++;
   dsu[it]=it;
   dsu[u]=it;
   dsu[v]=it;
   DG[it].pb(u);
   if(v!=u) DG[it].pb(v);
}

int pre[N+M],post[N+M],c;
int a1[N],a2[N];

void dfs(int v,bool b)
{
    if(sz(DG[v])==0)
    {
        pre[v]=++c;
        if(b) a2[c]=v;
        else a1[c]=v;
        post[v]=c;
    }
    else
    {
        pre[v]=inf;
        post[v]=0;
    }
    for(auto u:DG[v])
    {
        dfs(u,b);
        pre[v]=min(pre[v],pre[u]);
        post[v]=max(post[v],post[u]);
    }
}
int tree[4*N],pot=1;
vector<pair<pair<int,int>,pair<int,int>>>vec[N];
int que(int v,int a,int b,int l,int r)
{
    if(a<=l&&b>=r) return tree[v];
    if(l>b||r<a) return 0;
    return max(que(2*v,a,b,l,(l+r)/2),que(2*v+1,a,b,(l+r)/2+1,r));
}
void ins(int u,int v)
{
    int y=u+pot-1;
    tree[y]=v;
    while(y>1)
    {
        y/=2;
        tree[y]=max(tree[2*y],tree[2*y+1]);
    }
}


vector<int> check_validity(int n,vector<int> X,vector<int> Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R)
{
    for(int i=0;i<sz(X);i++)
    {
        X[i]++;
        Y[i]++;
        if(X[i]>Y[i])
        {
            G1[X[i]].pb(Y[i]);
            G[Y[i]].pb(X[i]);
        }
        else
        {
            G[X[i]].pb(Y[i]);
            G1[Y[i]].pb(X[i]);
        }
    }
    for(int i=0;i<sz(S);i++)
    {
        S[i]++;
        E[i]++;
        L[i]++;
        R[i]++;
        poc[L[i]].pb({S[i],i});
        kon[R[i]].pb({E[i],i});
    }
    it=n;
    for(int i=1;i<=n;i++) dsu[i]=i;
    for(int i=n;i>0;i--)
    {
        for(auto u:G[i]) Union(i,u);
        for(auto x:poc[i]) q[x.nd][0]=Find(x.st);
    }
    for(int i=1;i<=it;i++) if(Find(i)==i) dfs(i,0);
    for(int i=0;i<sz(S);i++) seg[i][0]={pre[q[i][0]],post[q[i][0]]};
    for(int i=1;i<=it;i++) DG[i].clear();
    it=n,c=0;
    for(int i=1;i<=n;i++) dsu[i]=i;
    for(int i=1;i<=n;i++)
    {
        for(auto u:G1[i]) Union(i,u);
        for(auto x:kon[i]) q[x.nd][1]=Find(x.st);
    }
    for(int i=1;i<=it;i++) if(Find(i)==i) dfs(i,1);
    for(int i=0;i<sz(S);i++) seg[i][1]={pre[q[i][1]],post[q[i][1]]};
    while(pot<n) pot*=2;
    for(int i=0;i<sz(S);i++)
    {
      //  cout<<seg[i][0].st<<" "<<seg[i][0].nd<<" "<<seg[i][1].st<<" "<<seg[i][1].nd<<endl;
        vec[seg[i][0].nd].pb({{seg[i][0].st,i},{seg[i][1].st,seg[i][1].nd}});
    }
    vector<int>ans(sz(S));
    for(int i=1;i<=n;i++)
    {
        ins(pre[a1[i]],i);
        for(auto x:vec[i])
        {
            //cout<<x.st.nd<<" "<<que(1,x.nd.st,x.nd.nd,1,pot)<<endl;
            if(que(1,x.nd.st,x.nd.nd,1,pot)>=x.st.st&&S[x.st.nd]>=L[x.st.nd]&&E[x.st.nd]<=R[x.st.nd]) ans[x.st.nd]=1;
        }
    }
    return ans;
}

/*int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int nn,mm,qq;
    cin>>nn>>mm>>qq;
    vector<int> xx(mm),yy(mm);
    for(int i=0;i<mm;i++) cin>>xx[i];
    for(int i=0;i<mm;i++) cin>>yy[i];
    vector<int> ss(qq),ee(qq),LL(qq),rr(qq);
    for(int i=0;i<qq;i++) cin>>ss[i];
    for(int i=0;i<qq;i++) cin>>ee[i];
    for(int i=0;i<qq;i++) cin>>LL[i];
    for(int i=0;i<qq;i++) cin>>rr[i];
    vector<int> veccc=check_validity(nn,xx,yy,ss,ee,LL,rr);
    for(auto x:veccc) cout<<x<<' ';

    return 0;
}*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 99052 KB Output is correct
2 Correct 68 ms 99052 KB Output is correct
3 Correct 67 ms 99052 KB Output is correct
4 Correct 67 ms 99052 KB Output is correct
5 Correct 66 ms 99052 KB Output is correct
6 Correct 67 ms 99052 KB Output is correct
7 Correct 69 ms 99052 KB Output is correct
8 Correct 67 ms 99052 KB Output is correct
9 Correct 68 ms 99052 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 99052 KB Output is correct
2 Correct 68 ms 99052 KB Output is correct
3 Correct 67 ms 99052 KB Output is correct
4 Correct 67 ms 99052 KB Output is correct
5 Correct 66 ms 99052 KB Output is correct
6 Correct 67 ms 99052 KB Output is correct
7 Correct 69 ms 99052 KB Output is correct
8 Correct 67 ms 99052 KB Output is correct
9 Correct 68 ms 99052 KB Output is correct
10 Correct 75 ms 99948 KB Output is correct
11 Correct 75 ms 99820 KB Output is correct
12 Correct 73 ms 99820 KB Output is correct
13 Correct 74 ms 100076 KB Output is correct
14 Correct 74 ms 100076 KB Output is correct
15 Correct 76 ms 100076 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 808 ms 148460 KB Output is correct
2 Correct 766 ms 156652 KB Output is correct
3 Correct 774 ms 151276 KB Output is correct
4 Correct 774 ms 148380 KB Output is correct
5 Correct 779 ms 148440 KB Output is correct
6 Correct 809 ms 148972 KB Output is correct
7 Correct 723 ms 145452 KB Output is correct
8 Correct 733 ms 156648 KB Output is correct
9 Correct 671 ms 149332 KB Output is correct
10 Correct 621 ms 147028 KB Output is correct
11 Correct 651 ms 147220 KB Output is correct
12 Correct 750 ms 147408 KB Output is correct
13 Correct 769 ms 159060 KB Output is correct
14 Correct 762 ms 159280 KB Output is correct
15 Correct 750 ms 159348 KB Output is correct
16 Correct 742 ms 159180 KB Output is correct
17 Correct 719 ms 145320 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 99052 KB Output is correct
2 Correct 68 ms 99052 KB Output is correct
3 Correct 67 ms 99052 KB Output is correct
4 Correct 67 ms 99052 KB Output is correct
5 Correct 66 ms 99052 KB Output is correct
6 Correct 67 ms 99052 KB Output is correct
7 Correct 69 ms 99052 KB Output is correct
8 Correct 67 ms 99052 KB Output is correct
9 Correct 68 ms 99052 KB Output is correct
10 Correct 75 ms 99948 KB Output is correct
11 Correct 75 ms 99820 KB Output is correct
12 Correct 73 ms 99820 KB Output is correct
13 Correct 74 ms 100076 KB Output is correct
14 Correct 74 ms 100076 KB Output is correct
15 Correct 76 ms 100076 KB Output is correct
16 Correct 808 ms 148460 KB Output is correct
17 Correct 766 ms 156652 KB Output is correct
18 Correct 774 ms 151276 KB Output is correct
19 Correct 774 ms 148380 KB Output is correct
20 Correct 779 ms 148440 KB Output is correct
21 Correct 809 ms 148972 KB Output is correct
22 Correct 723 ms 145452 KB Output is correct
23 Correct 733 ms 156648 KB Output is correct
24 Correct 671 ms 149332 KB Output is correct
25 Correct 621 ms 147028 KB Output is correct
26 Correct 651 ms 147220 KB Output is correct
27 Correct 750 ms 147408 KB Output is correct
28 Correct 769 ms 159060 KB Output is correct
29 Correct 762 ms 159280 KB Output is correct
30 Correct 750 ms 159348 KB Output is correct
31 Correct 742 ms 159180 KB Output is correct
32 Correct 719 ms 145320 KB Output is correct
33 Correct 845 ms 150124 KB Output is correct
34 Correct 568 ms 178064 KB Output is correct
35 Correct 928 ms 166124 KB Output is correct
36 Correct 839 ms 158932 KB Output is correct
37 Correct 868 ms 163584 KB Output is correct
38 Correct 875 ms 160464 KB Output is correct
39 Correct 839 ms 174316 KB Output is correct
40 Correct 981 ms 179300 KB Output is correct
41 Correct 781 ms 161256 KB Output is correct
42 Correct 703 ms 156008 KB Output is correct
43 Correct 969 ms 181356 KB Output is correct
44 Correct 819 ms 163564 KB Output is correct
45 Correct 744 ms 173644 KB Output is correct
46 Correct 745 ms 172776 KB Output is correct
47 Correct 748 ms 167884 KB Output is correct
48 Correct 733 ms 167320 KB Output is correct
49 Correct 740 ms 167864 KB Output is correct
50 Correct 729 ms 167372 KB Output is correct
51 Correct 954 ms 177944 KB Output is correct
52 Correct 956 ms 178024 KB Output is correct