Submission #1082007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082007		TlenekWodoru	Thousands Islands (IOI22_islands)	C++17	100 / 100	103 ms	40280 KiB

islands

#include<bits/stdc++.h>
#include "islands.h"
#include <variant>
using namespace std;
vector<int>D[200009];
vector<int>Num[200009];
vector<int>T[200009];
vector<int>Num2[200009];
int n,m;
bool usu[200009];
int stopien[200009];
bool zaj[200009];
int Next[200009],NextNum[200009];
bool CzyCykl[200009];
vector<int>A,U;
void UsuVert(int v)
{
    usu[v]=1;
    for(int som : T[v])
    {
        stopien[som]--;
        if(usu[som]==0&&stopien[som]==0){U.push_back(som);}
    }
}
void VectorAdd(vector<int>&Odp,const vector<int>&Dod, bool CzyRevers=0)
{
    if(CzyRevers==0)
    {
        for(int u : Dod)
        {
            Odp.push_back(u);
        }
    }
    else
    {
        for(int i=(int)Dod.size()-1;i>=0;i--)
        {
            Odp.push_back(Dod[i]);
        }
    }
}
void coutt(string A, vector<int>AA)
{
    cout<<A<<"=";
    for(int u : AA)
    {
        cout<<u<<',';
    }
    cout<<endl;
}
variant<bool, vector<int>> find_journey(
    int N, int M, vector<int> E1, vector<int> E2)
{
    n=N;
    m=M;
    for(int i=0;i<m;i++)
    {
        stopien[E1[i]]++;
        D[E1[i]].push_back(E2[i]);
        Num[E1[i]].push_back(i);
        T[E2[i]].push_back(E1[i]);
        Num2[E2[i]].push_back(i);
    }
    for(int i=0;i<n;i++)
    {
        if(stopien[i]==0)
        {
            U.push_back(i);
        }
    }
    int start=0;
    while(true)
    {
        if((int)U.size()>0)
        {
            const int u=U.back();
            U.pop_back();
            UsuVert(u);
        }
        else if(stopien[start]==1)
        {
            int som=-1,ind=-1;
            for(int i=0;i<(int)D[start].size();i++)
            {
                som=D[start][i];
                ind=Num[start][i];
                if(usu[som]==0){break;}
            }
            UsuVert(start);
            A.push_back(ind);
            start=som;
        }
        else{break;}
    }
    if(usu[start]){return false;}
    memset(Next,-1,sizeof(Next));
    memset(NextNum,-1,sizeof(NextNum));
    vector<int>V1,K1,Droga1,Cykl1;
    vector<int>V2,K2,Droga2,Cykl2;
    int v;
    v=start;
    int casee=-1,spotkanie=-1;
    while(true)
    {
        int som=-1,ind=-1;
        for(int i=0;i<(int)D[v].size();i++)
        {
            som=D[v][i];
            ind=Num[v][i];
            if(usu[som]==0){break;}
        }
        zaj[v]=1;
        Next[v]=som;
        NextNum[v]=ind;
        V1.push_back(v);
        K1.push_back(ind);
        if(zaj[som])
        {
            spotkanie=som;
            while(true)
            {
                bool czyBreak=0;
                if(V1.back()==som){czyBreak=1;}
                CzyCykl[V1.back()]=1;
                Cykl1.push_back(K1.back());
                V1.pop_back();
                K1.pop_back();
                if(czyBreak){break;}
            }
            reverse(Cykl1.begin(),Cykl1.end());
            Droga1=K1;
            break;
        }
        v=som;
    }
    v=start;
    while(true)
    {
        int som=-1,ind=-1;
        for(int i=D[v].size()-1;i>=0;i--)
        {
            som=D[v][i];
            ind=Num[v][i];
            if(usu[som]==0){break;}
        }
        zaj[v]=1;
        V2.push_back(v);
        K2.push_back(ind);
        if(zaj[som])
        {
            if(Next[som]==-1)
            {
                while(true)
                {
                    bool czyBreak=0;
                    if(V2.back()==som){czyBreak=1;}
                    Cykl2.push_back(K2.back());
                    V2.pop_back();
                    K2.pop_back();
                    if(czyBreak){break;}
                }
                reverse(Cykl2.begin(),Cykl2.end());
                Droga2=K2;
                casee=1;
            }
            else
            {
                v=som;
                if(CzyCykl[v])
                {
                    Droga2=K2;
                    int v2=v;
                    while(true)
                    {
                        Cykl2.push_back(NextNum[v2]);
                        v2=Next[v2];
                        if(v2==v){break;}
                    }
                }
                else
                {
                    while(v!=spotkanie)
                    {
                        V2.push_back(Next[v]);
                        K2.push_back(NextNum[v]);
                        v=Next[v];
                    }
                    Droga2=K2;
                    Cykl2=Cykl1;
                }
                casee=2;
            }
            break;
        }
        v=som;
    }
    vector<int>Odp;
    VectorAdd(Odp,A);
    if(casee==1)
    {
        VectorAdd(Odp,K1);
        VectorAdd(Odp,Cykl1);
        VectorAdd(Odp,K1,1);
        VectorAdd(Odp,K2);
        VectorAdd(Odp,Cykl2);
        VectorAdd(Odp,K2,1);
        VectorAdd(Odp,K1);
        VectorAdd(Odp,Cykl1,1);
        VectorAdd(Odp,K1,1);
        VectorAdd(Odp,K2);
        VectorAdd(Odp,Cykl2,1);
        VectorAdd(Odp,K2,1);
    }
    else if(casee==2)
    {
        VectorAdd(Odp,K1);
        VectorAdd(Odp,Cykl1);
        VectorAdd(Odp,K1,1);
        VectorAdd(Odp,K2);
        VectorAdd(Odp,Cykl2,1);
        VectorAdd(Odp,K2,1);
    }
    VectorAdd(Odp,A,1);
    return Odp;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 24 / 24
• Subtask 5: 45 / 45