Submission #1085209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085209		TlenekWodoru	Werewolf (IOI18_werewolf)	C++17	100 / 100	1503 ms	295528 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
struct ZAP
{
    int v,ind;
};
vector<int>D[200009];
vector<int>S[4009];
bool Nawiazanie[4009];
vector<ZAP>Q1[200009],Q2[200009];
int spojna[200009];
vector<int>V[200009],V2[200009];
int JakieS[200009];
vector<int>Z1[200009],Z2[200009];
int Z1s[200009],Z2s[200009];
bool CzyNachodzi[4009][4009];
bool help[200009];
int n,m,q,SQRT=223,h=0;
void Polacz(int a, int b)
{
    a=spojna[a];
    b=spojna[b];
    if(a==b){return;}
    if(V2[a].size()<V2[b].size()){swap(a,b);}
    for(int u : V[b])
    {
        V[a].push_back(u);
    }
    for(int u : V2[b])
    {
        spojna[u]=a;
        V2[a].push_back(u);
    }
    V[b].clear();
    V2[b].clear();
    vector<int>Pier;
    if(JakieS[a]!=-1){Pier.push_back(JakieS[a]);}
    if(JakieS[b]!=-1){Pier.push_back(JakieS[b]);}
    if((int)V[a].size()>=SQRT)
    {
        h++;
        for(int i=1;i<=SQRT;i++)
        {
            S[h].push_back(V[a].back());
            V[a].pop_back();
        }
        Pier.push_back(h);
    }
    while((int)Pier.size()>1)
    {
        const int aa=Pier[Pier.size()-2];
        const int bb=Pier[Pier.size()-1];
        Pier.pop_back();
        Pier.pop_back();
        h++;
        Pier.push_back(h);
        Nawiazanie[h]=1;
        S[h]={aa,bb};
    }
    if((int)Pier.size()==0){JakieS[a]=-1;}
    else{JakieS[a]=Pier[0];}
}
void Polacz2(int a, int b)
{
    a=spojna[a];
    b=spojna[b];
    if(a==b){return;}
    if(V[a].size()<V[b].size()){swap(a,b);}
    for(int u : V[b])
    {
        spojna[u]=a;
        V[a].push_back(u);
    }
    V[b].clear();
}
vector<int>check_validity(int N, vector<int>E1, vector<int>E2, vector<int>AA, vector<int>BB, vector<int>LL, vector<int>RR)
{
    n=N;
    m=E1.size();
    q=AA.size();
    vector<int>ODP(q);
    //SQRT=max(2,(int)sqrt(n));
    for(int i=0;i<m;i++)
    {
        const int a=E1[i],b=E2[i];
        D[a].push_back(b);
        D[b].push_back(a);
    }
    for(int i=0;i<q;i++)
    {
        Q1[RR[i]].push_back({BB[i],i});
        Q2[LL[i]].push_back({AA[i],i});
    }
    memset(JakieS,-1,sizeof(JakieS));
    for(int i=0;i<n;i++){spojna[i]=i;V[i]={i};V2[i]={i};}
    for(int i=0;i<n;i++)
    {
        for(int som : D[i])
        {
            if(som<=i)
            Polacz(i,som);
        }
        for(auto[v,ind] : Q1[i])
        {
            Z1[ind]=V[spojna[v]];
            Z1s[ind]=JakieS[spojna[v]];
        }
    }
    memset(JakieS,-1,sizeof(JakieS));
    for(int i=0;i<n;i++){spojna[i]=i;V[i]={i};V2[i]={i};}
    for(int i=n-1;i>=0;i--)
    {
        for(int som : D[i])
        {
            if(som>=i)
            Polacz(i,som);
        }
        for(auto[v,ind] : Q2[i])
        {
            Z2[ind]=V[spojna[v]];
            Z2s[ind]=JakieS[spojna[v]];
        }
    }
    for(int i=1;i<=h;i++)
    {
        CzyNachodzi[i][i]=1;
        if(Nawiazanie[i]){continue;}
        for(int j=i+1;j<=h;j++)
        {
            if(Nawiazanie[j]){continue;}
            for(int u : S[i])
            {
                help[u]=1;
            }
            bool cv=0;
            for(int u : S[j])
            {
                if(help[u])
                {
                    cv=1;
                    break;
                }
            }
            CzyNachodzi[i][j]=cv;
            CzyNachodzi[j][i]=cv;
            for(int u : S[i])
            {
                help[u]=0;
            }
        }
    }
    /**for(int i=1;i<=h;i++)
    {
        if(Nawiazanie[i])
        {
            cout<<"i="<<i<<" a="<<S[i][0]<<" b="<<S[i][1]<<endl;
        }
        else
        {
            cout<<"i="<<i<<"| ";
            for(int u : S[i])
            {
                cout<<u<<",";
            }
            cout<<endl;
        }
    }**/
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<i;j++)
        {
            bool cv;
            if(Nawiazanie[i]==0&&Nawiazanie[j]==0){continue;}
            if(Nawiazanie[j]==0)
            {
                cv=(CzyNachodzi[j][S[i][0]]|CzyNachodzi[j][S[i][1]]);
            }
            else if(Nawiazanie[i]==0)
            {
                cv=(CzyNachodzi[i][S[j][0]]|CzyNachodzi[i][S[j][1]]);
            }
            else
            {
                cv=(CzyNachodzi[S[i][0]][S[j][0]]|CzyNachodzi[S[i][0]][S[j][1]]|
                    CzyNachodzi[S[i][1]][S[j][0]]|CzyNachodzi[S[i][1]][S[j][1]]);
            }
            CzyNachodzi[i][j]=cv;
            CzyNachodzi[j][i]=cv;
        }
    }
    memset(JakieS,-1,sizeof(JakieS));
    for(int i=0;i<n;i++){spojna[i]=i;V[i]={i};}
    for(int i=0;i<n;i++)
    {
        for(int som : D[i])
        {
            if(som<=i)
            Polacz2(i,som);
        }
        for(auto[v,ind] : Q1[i])
        {
            int s=spojna[v];
            for(int u : Z2[ind])
            {
                if(spojna[u]==s)
                {
                    ODP[ind]=1;
                    break;
                }
            }
        }
    }
    memset(JakieS,-1,sizeof(JakieS));
    for(int i=0;i<n;i++){spojna[i]=i;V[i]={i};}
    for(int i=n-1;i>=0;i--)
    {
        for(int som : D[i])
        {
            if(som>=i)
            Polacz2(i,som);
        }
        for(auto[v,ind] : Q2[i])
        {
            int s=spojna[v];
            for(int u : Z1[ind])
            {
                if(spojna[u]==s)
                {
                    ODP[ind]=1;
                    break;
                }
            }
        }
    }
    for(int i=0;i<q;i++)
    {
        if(Z1s[i]==-1||Z2s[i]==-1){continue;}
        if(CzyNachodzi[Z1s[i]][Z2s[i]])
        {
            ODP[i]=1;
        }
    }
    for(int i=0;i<q;i++)
    {
        if(AA[i]<LL[i]||RR[i]<BB[i]){ODP[i]=0;}
    }
    return ODP;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51