Submission #1076476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076476		Ignut	Thousands Islands (IOI22_islands)	C++17	12.35 / 100	84 ms	18108 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;

    if (!idx.count({lst, X})) n /= 0;
    if (!idx.count({lst, Y})) n /= 0;
    if (!idx.count({Y, lst})) n /= 0;
    if (!idx.count({X, lst})) n /= 0;

    int A = idx[{lst, X}];
    int B = idx[{X, lst}];
    int C = idx[{lst, Y}];
    int D = idx[{Y, lst}];
    res.push_back(A);
    res.push_back(B);
    res.push_back(C);
    res.push_back(D);

    res.push_back(B);
    res.push_back(A);
    res.push_back(D);
    res.push_back(C);

    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;
      |                             ~~^~~~
islands.cpp:82:33: warning: division by zero [-Wdiv-by-zero]
   82 |     if (!idx.count({lst, X})) n /= 0;
      |                               ~~^~~~
islands.cpp:83:33: warning: division by zero [-Wdiv-by-zero]
   83 |     if (!idx.count({lst, Y})) n /= 0;
      |                               ~~^~~~
islands.cpp:84:33: warning: division by zero [-Wdiv-by-zero]
   84 |     if (!idx.count({Y, lst})) n /= 0;
      |                               ~~^~~~
islands.cpp:85:33: warning: division by zero [-Wdiv-by-zero]
   85 |     if (!idx.count({X, lst})) n /= 0;
      |                               ~~^~~~

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