Submission #1081901

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081901		TlenekWodoru	Thousands Islands (IOI22_islands)	C++17	35 / 100	147 ms	38472 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];
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);}
    }
}
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;}
    return true;
}

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