Submission #1037604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037604		12345678	Thousands Islands (IOI22_islands)	C++17	24 / 100	73 ms	4940 KiB

islands

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

using namespace std;

const int nx=1e3+5;

int ans, vs[nx];
vector<pair<int, int>> d[nx];
vector<int> l, res;
pair<int, int> pa[nx], pa2[nx];

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

void dfs2(int u, int rt)
{
    vs[u]=1;
    for (auto [v, idx]:d[u]) 
    {
        if (!ans&&v==rt)
        {
            vector<int> tmp, path;
            int cur=rt;
            while (cur!=0) tmp.push_back(pa[cur].second), cur=pa[cur].first;
            reverse(tmp.begin(), tmp.end());
            for (auto x:tmp) res.push_back(x);
            reverse(tmp.begin(), tmp.end());
            cur=u;
            path.push_back(idx);
            while (cur!=rt) path.push_back(pa2[cur].second), cur=pa[cur].first;
            reverse(path.begin(), path.end());
            for (auto x:path) res.push_back(x);
            for (auto x:path) res.push_back(x+1);
            reverse(path.begin(), path.end());
            for (auto x:path) res.push_back(x);
            for (auto x:path) res.push_back(x+1);
            for (auto x:tmp) res.push_back(x);
            ans=1;
        }
        if (vs[v]) continue;
        else pa2[v]={u, idx}, dfs2(v, rt);
    }
}

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.first==V[i]) f=1;
        if (!f) d[U[i]].push_back({V[i], 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 res;
    return false;
}

/*
5 10
0 1
0 1
1 2
1 2
2 3
2 3
3 4
3 4
4 2
4 2
*/

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