Submission #631830

#	Time	Username	Problem	Language	Result	Execution time	Memory
631830		4123xr4323	Thousands Islands (IOI22_islands)	C++17	1.75 / 100	37 ms	12616 KiB

islands

#include <bits/stdc++.h>
#define mp make_pair
#define all(a) a.begin(),a.end()
#define X first
#define Y second
using namespace std;
using pii = pair <long long, long long>;
constexpr int maxn = 2e5 + 10;
constexpr int mod = 1000002022;
constexpr long long inf = 1e17 + 10;

int n, m;
vector <pii> graph [maxn];
bool used [maxn], stop = false;
pii parent [maxn];

inline void dfs (int v) {
    if (v == 0 && used[v]) stop = true;
    if (stop) return;
    used[v] = true;
    for (pii i : graph[v]) {
        if (used[i.X] && i.X != 0) continue;
        if (used[i.X] && parent[v].X == i.X) continue;
        parent[i.X] = mp (v, i.Y);
        dfs (i.X);
        if (stop) return;
    }
} 

vector <int> res = {};

inline void goodbye () {
    vector <int> A = {};
    int v = 0;
    while (v != 0 || A.empty ()) {
        A.push_back (parent[v].Y);
        v = parent[v].X;
    }
    reverse (all (A));
    for (int i : A) res.push_back (i);
    for (int i : A) res.push_back (i ^ 1);
    reverse (all (A));
    for (int i : A) res.push_back (i);
    for (int i : A) res.push_back (i);
}

int am1 [maxn], am2 [maxn];

variant <bool, vector <int>> find_journey (int N, int M, vector <int> U, vector <int> V) {
    n = N, m = M;
    for (int i = 0; i < m; ++i) {
        graph[U[i]].push_back (mp (V[i], i));
    }
    dfs (0);
    if (stop) {
        goodbye ();
        return res;
    }
    for (int i = 0; i < m; ++i) if (min (V[i], U[i]) == 0) {
        ++am1[U[i]];
        ++am2[V[i]];
    }
    int ver = -1;
    for (int i = 1; i < n; ++i) {
        if (am1[i] >= 2 && am2[i] >= 1) ver = i;
    }
    if (ver == -1) return false;
    int a1 = -1, a2, a3;
    for (int i = 0; i < m; ++i)  if (V[i] == 0 && U[i] == ver) {
        if (a1 == -1) a1 = i;
        else a2 = i;
    }
    for (int i = 0; i < m; ++i)  if (U[i] == 0 && V[i] == ver) {
        a3 = i;
        break;
    }
    res = {a1, a3, a2, a1, a3, a2};
    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:77:9: warning: 'a2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |     res = {a1, a3, a2, a1, a3, a2};
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
islands.cpp:77:9: warning: 'a3' may be used uninitialized in this function [-Wmaybe-uninitialized]

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