제출 #1079547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1079547		TlenekWodoru	수천개의 섬 (IOI22_islands)	C++17	11.90 / 100	71 ms	40788 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 spojna[200009];
vector<int>V[200009];
vector<pair<int,int>>Ziomek[200009];
bool zaj[200009];
bool CzyGit[200009];
int JakiTyp[200009][2];
pair<int,int>Last[200009][2];
int LastNum[200009][2];
int Last2[200009],Last2Num[200009];
bool CzyCykl[200009];
vector<int>U;
int h=0,n,m;
void DFS(int v)
{
    if(zaj[v]){return;}
    zaj[v]=1;
    for(int som : D[v])
    {
        DFS(som);
    }
    U.push_back(v);
}
void DFS2(int v)
{
    if(spojna[v]!=0){return;}
    spojna[v]=h;
    V[h].push_back(v);
    for(int som : T[v])
    {
        DFS2(som);
    }
}
void DFS3(int v, int u)
{
    for(int i=0;i<(int)D[v].size();i++)
    {
        const int som=D[v][i];
        const int ind=Num[v][i];
        int z=JakiTyp[v][u];
        if(v==0){z=ind;}
        if(JakiTyp[som][0]==-1)
        {
            JakiTyp[som][0]=z;
            Last[som][0]={v,u};
            LastNum[som][0]=ind;
            DFS3(som,0);
        }
        else if(JakiTyp[som][1]==-1&&JakiTyp[som][0]!=z)
        {
            JakiTyp[som][1]=z;
            Last[som][1]={v,u};
            LastNum[som][1]=ind;
            DFS3(som,1);
        }
    }
}
void DFS4(int v)
{
    for(int i=0;i<(int)T[v].size();i++)
    {
        const int som=T[v][i];
        const int ind=Num2[v][i];
        if(Last2[som]!=-1||spojna[v]!=spojna[som]){continue;}
        Last2[som]=v;
        Last2Num[som]=ind;
        DFS4(som);
    }
}
void SSS()
{
    for(int i=0;i<n;i++)
    {
        DFS(i);
    }
    reverse(U.begin(),U.end());
    for(int u : U)
    {
        if(spojna[u]==0)
        {
            h++;
            DFS2(u);
        }
    }
}
void VectorAdd(vector<int>&A, const vector<int>&B)
{
    for(int u : B)
    {
        A.push_back(u);
    }
}
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++)
    {
        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);
    }
    SSS();
    for(int i=0;i<n;i++)
    {
        int ile=0;
        for(int som : D[i])
        {
            if(spojna[i]!=spojna[som]){continue;}
            ile++;
        }
        CzyGit[i]=(ile>=2);
    }
    for(int i=0;i<n;i++)
    {
        Last[i][0]={-1,-1};
        Last[i][1]={-1,-1};
    }
    memset(Last2,-1,sizeof(Last2));
    memset(JakiTyp,-1,sizeof(JakiTyp));
    JakiTyp[0][0]=0;
    JakiTyp[0][1]=0;
    DFS3(0,0);
    JakiTyp[0][1]=-1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<2;j++)
        {
            if(JakiTyp[i][j]!=-1&&spojna[i]!=spojna[Last[i][j].first]&&(int)Ziomek[spojna[i]].size()<2)
            {
                Ziomek[spojna[i]].push_back({i,j});
            }
        }
    }
    vector<int>Odp;
    for(int i=1;i<=h;i++)
    {
        int a,b,u1,u2,v,u;
        if((int)Ziomek[i].size()==0){continue;}
        vector<int>A,B,Cykl1,Cykl2,Droga;
        if((int)Ziomek[i].size()==1)
        {
            if(CzyGit[Ziomek[i][0].first]==0){continue;}
            v=Ziomek[i][0].first;
            u1=Ziomek[i][0].second;
            DFS4(v);
            int v2=v;
            while(true)
            {
                CzyCykl[v2]=1;
                Cykl1.push_back(Last2Num[v2]);
                v2=Last2[v2];
                if(v==v2){break;}
            }
            for(int i=0;i<(int)D[v].size();i++)
            {
                const int som=D[v][i];
                const int ind=Num[v][i];
                if(spojna[v]!=spojna[som]||Last2Num[v]==ind){continue;}
                Droga.push_back(ind);
                v2=som;
            }
            int spotkanie=-1;
            while(true)
            {
                if(spotkanie==v2){break;}
                if(spotkanie==-1&&CzyCykl[v2]){spotkanie=v2;}
                if(spotkanie==-1){Droga.push_back(Last2Num[v2]);}
                else{Cykl2.push_back(Last2Num[v2]);}
                v2=Last2[v2];
            }
            reverse(Cykl2.begin(),Cykl2.end());
            v2=v;
            while(v2!=0)
            {
                A.push_back(LastNum[v2][u]);
                tie(v2,u)=Last[v2][u];
            }
            reverse(A.begin(),A.end());
            VectorAdd(Odp,A);
            VectorAdd(Odp,Cykl1);
            VectorAdd(Odp,Droga);
            VectorAdd(Odp,Cykl2);
            reverse(Droga.begin(),Droga.end());
            VectorAdd(Odp,Droga);
            reverse(A.begin(),A.end());
            VectorAdd(Odp,A);
            return Odp;
        }
        else if(V[i].size()>1)
        {
            a=Ziomek[i][0].first;u1=Ziomek[i][0].second;
            b=Ziomek[i][1].first;u2=Ziomek[i][1].second;
            DFS4(a);
            v=a;
            while(true)
            {
                CzyCykl[v]=1;
                Cykl1.push_back(Last2Num[v]);
                v=Last2[v];
                if(v==a){break;}
            }
            v=b;
            int spotkanie=-1;
            while(true)
            {
                if(v==spotkanie){break;}
                if(spotkanie==-1&&CzyCykl[v]){spotkanie=v;}
                if(spotkanie==-1){Droga.push_back(Last2Num[v]);}
                else{Cykl2.push_back(Last2Num[v]);}
                v=Last2[v];
            }
            reverse(Cykl2.begin(),Cykl2.end());
            v=a;
            u=u1;
            while(v!=0)
            {
                A.push_back(LastNum[v][u]);
                tie(v,u)=Last[v][u];
            }
            reverse(A.begin(),A.end());
            v=b;
            u=u2;
            while(v!=0)
            {
                B.push_back(LastNum[v][u]);
                tie(v,u)=Last[v][u];
            }
            reverse(B.begin(),B.end());
            VectorAdd(Odp,A);
            VectorAdd(Odp,Cykl1);
            reverse(A.begin(),A.end());
            VectorAdd(Odp,A);
            VectorAdd(Odp,B);
            VectorAdd(Odp,Droga);
            VectorAdd(Odp,Cykl2);
            reverse(Droga.begin(),Droga.end());
            VectorAdd(Odp,Droga);
            reverse(B.begin(),B.end());
            VectorAdd(Odp,B);
            return Odp;
        }
    }
    return false;
}

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