제출 #1081991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1081991		TlenekWodoru	수천개의 섬 (IOI22_islands)	C++17	31 / 100	1122 ms	889620 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 Last[200009],LastNum[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]);
        }
    }
}

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(Last,-1,sizeof(Last));
    memset(LastNum,-1,sizeof(LastNum));
    vector<int>V1,K1,Droga1,Cykl1;
    vector<int>V2,K2,Droga2,Cykl2;
    int v;
    v=start;
    int casee=-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;
        Last[som]=v;
        LastNum[som]=ind;
        V1.push_back(v);
        K1.push_back(ind);
        if(zaj[som])
        {
            while(true)
            {
                bool czyBreak=0;
                if(V1.back()==som){czyBreak=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(Last[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
            {
                Droga2=K2;
                v=som;
                while(true)
                {
                    Cykl2.push_back(LastNum[v]);
                    v=Last[v];
                    if(v==som){break;}
                }
                reverse(Cykl2.begin(),Cykl2.end());
                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: 0 / 24
• Subtask 5: 0 / 45