Submission #1037538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037538		12345678	Thousands Islands (IOI22_islands)	C++17	0 / 100	5 ms	348 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1e3+5;

int ans, vs[nx];
vector<int> d[nx], l;

void dfs(int u)
{
    vs[u]=1;
    l.push_back(u);
    for (auto v:d[u]) if (!vs[v]) dfs(v);
}

void dfs2(int u, int rt)
{
    vs[u]=1;
    for (auto v:d[u]) 
    {
        if (v==rt) ans=1;
        if (vs[v]) continue;
        else dfs2(v, u);
    }
}

std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
    for (int i=0; i<M; i+=2) 
    {
        bool f=0;
        for (auto x:d[U[i]]) if (x==V[i]) f=1;
        if (!f) d[U[i]].push_back(V[i]);
    }
    dfs(0);
    for (auto x:l) 
    {
        if (!ans) 
        {
            for (int i=0; i<N; i++) vs[i]=0;
            dfs2(x, x);
        }
    }
    if (ans) return vector<int> {};
    return false;
}

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