oj.uz

Submission #359342

# Submission time Handle Problem Language Result Execution time Memory
359342 2021-01-26T22:30:23 Z Rafi22 Werewolf (IOI18_werewolf) C++14
49 / 100
 809 ms 284044 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=400007,M=600007,Q=400007;
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 48 ms 70892 KB Output is correct
2 Correct 48 ms 70848 KB Output is correct
3 Correct 48 ms 70892 KB Output is correct
4 Correct 48 ms 70892 KB Output is correct
5 Correct 50 ms 70796 KB Output is correct
6 Correct 48 ms 70892 KB Output is correct
7 Correct 48 ms 71020 KB Output is correct
8 Correct 48 ms 70892 KB Output is correct
9 Correct 48 ms 70892 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 70892 KB Output is correct
2 Correct 48 ms 70848 KB Output is correct
3 Correct 48 ms 70892 KB Output is correct
4 Correct 48 ms 70892 KB Output is correct
5 Correct 50 ms 70796 KB Output is correct
6 Correct 48 ms 70892 KB Output is correct
7 Correct 48 ms 71020 KB Output is correct
8 Correct 48 ms 70892 KB Output is correct
9 Correct 48 ms 70892 KB Output is correct
10 Correct 56 ms 71660 KB Output is correct
11 Correct 55 ms 71660 KB Output is correct
12 Correct 55 ms 71532 KB Output is correct
13 Correct 56 ms 71916 KB Output is correct
14 Correct 55 ms 71788 KB Output is correct
15 Correct 57 ms 71916 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 809 ms 120428 KB Output is correct
2 Correct 746 ms 136684 KB Output is correct
3 Correct 759 ms 131564 KB Output is correct
4 Correct 749 ms 128472 KB Output is correct
5 Correct 751 ms 128344 KB Output is correct
6 Correct 782 ms 129056 KB Output is correct
7 Correct 697 ms 125588 KB Output is correct
8 Correct 710 ms 136428 KB Output is correct
9 Correct 641 ms 129364 KB Output is correct
10 Correct 607 ms 126932 KB Output is correct
11 Correct 629 ms 127184 KB Output is correct
12 Correct 700 ms 127436 KB Output is correct
13 Correct 717 ms 139004 KB Output is correct
14 Correct 716 ms 139064 KB Output is correct
15 Correct 710 ms 139084 KB Output is correct
16 Correct 706 ms 139212 KB Output is correct
17 Correct 695 ms 125352 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 70892 KB Output is correct
2 Correct 48 ms 70848 KB Output is correct
3 Correct 48 ms 70892 KB Output is correct
4 Correct 48 ms 70892 KB Output is correct
5 Correct 50 ms 70796 KB Output is correct
6 Correct 48 ms 70892 KB Output is correct
7 Correct 48 ms 71020 KB Output is correct
8 Correct 48 ms 70892 KB Output is correct
9 Correct 48 ms 70892 KB Output is correct
10 Correct 56 ms 71660 KB Output is correct
11 Correct 55 ms 71660 KB Output is correct
12 Correct 55 ms 71532 KB Output is correct
13 Correct 56 ms 71916 KB Output is correct
14 Correct 55 ms 71788 KB Output is correct
15 Correct 57 ms 71916 KB Output is correct
16 Correct 809 ms 120428 KB Output is correct
17 Correct 746 ms 136684 KB Output is correct
18 Correct 759 ms 131564 KB Output is correct
19 Correct 749 ms 128472 KB Output is correct
20 Correct 751 ms 128344 KB Output is correct
21 Correct 782 ms 129056 KB Output is correct
22 Correct 697 ms 125588 KB Output is correct
23 Correct 710 ms 136428 KB Output is correct
24 Correct 641 ms 129364 KB Output is correct
25 Correct 607 ms 126932 KB Output is correct
26 Correct 629 ms 127184 KB Output is correct
27 Correct 700 ms 127436 KB Output is correct
28 Correct 717 ms 139004 KB Output is correct
29 Correct 716 ms 139064 KB Output is correct
30 Correct 710 ms 139084 KB Output is correct
31 Correct 706 ms 139212 KB Output is correct
32 Correct 695 ms 125352 KB Output is correct
33 Correct 803 ms 130284 KB Output is correct
34 Runtime error 727 ms 284044 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -