Submission #1236924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236924		countless	수천개의 섬 (IOI22_islands)	C++20	12.35 / 100	96 ms	23688 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    vector<vector<pair<int, int>>> adj(N), rev(N);
    vector<int> out(N);
    map<pair<int, int>, vector<int>> loc;
    map<pair<int, int>, int> use;
    for (int i = 0; i < M; i++) {
        adj[U[i]].emplace_back(V[i], i);
        rev[V[i]].emplace_back(U[i], i);
        out[U[i]]++;
        loc[{U[i], V[i]}].push_back(i);
    }

    // FIND ANY EDGE WITH DEGREE 2
    int start = -1;

    vector<int> ans;
    if (out[0] >= 2) {
        start = 0;
        int left = adj[0][0].first;
        int right = adj[0][1].first;

        int a, b, c, d;
        a = loc[{0, left}].front(), b = loc[{left, 0}].front();
        c = loc[{0, right}].front(), d = loc[{right, 0}].front();
        
        ans = {a, b, c, d, b, a, d, c};
        return ans;
    }

    if (start == -1) {
        vector<bool> vis(N);
        vector<int> par(N, -1);
        queue<int> q;
        vis[0] = true;
        q.emplace(0);

        while (!q.empty()) {
            auto u = q.front(); q.pop();

            for (auto &[v, i] : adj[u]) {
                if (!vis[v]) {
                    par[v] = u;
                    vis[v] = true;
                    q.emplace(v);
                    if (out[v] >= 3) {
                        start = v;
                        break;
                    }
                }
            }
        }

        if (start == -1) return false;

        int at = start;
        vector<int> path;
        while (at != -1) {
            // cerr << at sp par[at] << endl;
            path.push_back(at);
            at = par[at];
        }

        int m = path.size();
        for (int i = m-1; i >= 1; i--) {
            int u = path[i], v = path[i-1];
            ans.push_back(loc[{u, v}].front());
            use[{u, v}]++;
        }

        vector<int> cands;
        bool ok = false;
        for (int i = 0; i < adj[start].size(); i++) {
            if (!ok and adj[start][i].first == par[start]) {
                ok = true;
                continue;
            }
            cands.push_back(adj[start][i].first);
        }

        int left = cands[0], right = cands[1];
        int a, b, c, d;
        a = loc[{start, left}][use[{start, left}]++], b = loc[{left, start}][use[{left, start}]++];
        c = loc[{start, right}][use[{start, right}]], d = loc[{right, start}][use[{right, start}]];

        vector<int> temp = {a, b, c, d, b, a, d, c};
        for (auto &x : temp) ans.push_back(x);

        for (int i = 0; i < m-1; i++) {
            // cerr << i sp m-1 << endl;
            int u = path[i], v = path[i+1];
            ans.push_back(loc[{u, v}].front());
        }

        return ans;
    }

    return false;
}

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