Submission #1076462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076462		Ignut	Thousands Islands (IOI22_islands)	C++17	12.35 / 100	85 ms	18004 KiB

islands

/* Ignut
started: 11.08.2024
now: 26.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
const int MAXN = 1e5 + 123;
int n;
 
vector<pair<int, int>> g[MAXN];
 
vector<int> order;
 
int cycle_start = -1;
 
bool ans = false;

int lst = -1;
int X = -1, Y = -1;

void dfs(int v, int prev) {
    if (ans) return;
    if ((v == 0) + g[v].size() >= 3) {
        lst = v;
        ans = true;
        for (auto [to, e] : g[v]) {
            if (to == prev) continue;
            if (X == -1) X = to;
            else if (Y == -1) Y = to;
        }
        return;
    }
    for (auto [to, e] : g[v]) {
        if (to == prev) continue;
        order.push_back(e);
        dfs(to, v);
    }
}
 
int cnt[MAXN] = {};
 
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    n = N;
    map<pair<int, int>, int> idx;
    for (int i = 0; i < M; i ++) {
        g[U[i]].push_back({V[i], i});
        // g[V[i]].push_back(U[i]);
        idx[{U[i], V[i]}] = i;
    }
    dfs(0, -1);
    if (!ans) return false;
    if (X == -1 || Y == -1) n /= 0;

    vector<int> res = order;
    res.push_back(idx[{lst, X}]);
    res.push_back(idx[{X, lst}]);
    res.push_back(idx[{lst, Y}]);
    res.push_back(idx[{Y, lst}]);

    res.push_back(idx[{X, lst}]);
    res.push_back(idx[{lst, X}]);
    res.push_back(idx[{Y, lst}]);
    res.push_back(idx[{lst, Y}]);

    while (!order.empty()) {
        res.push_back(order.back());
        order.pop_back();
    }

    return res;
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:78:31: warning: division by zero [-Wdiv-by-zero]
   78 |     if (X == -1 || Y == -1) n /= 0;
      |                             ~~^~~~

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