Submission #1183765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183765		gyg	Thousands Islands (IOI22_islands)	C++20	0 / 100	51 ms	14796 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vec vector 
#define var variant
#define pii pair<int, int>
#define fir first 
#define sec second
const int N = 1e5 + 5;

int n, m;
arr<vec<int>, N> adj;
map<pii, int> id;

vec<int> stk, cyc;
arr<bool, N> vs;
bool dfs(int u = 1) {
    vs[u] = true;
    stk.push_back(u);
    for (int v : adj[u]) {
        if (!vs[v])  {
            if (dfs(v)) return true;
            continue;
        }
        while (true) {
            int w = stk.back(); stk.pop_back();
            cyc.push_back(w);
            if (w == v) break;
        }
        reverse(cyc.begin(), cyc.end());
        return true;
    }
    stk.pop_back();
    return false;
}

var<bool, vec<int>> find_journey(int _n, int _m, vec<int> _u, vec<int> _v) {
    n = _n, m = _m;
    for (int i = 0; i < m; i++) {
        int u = _u[i] + 1, v = _v[i] + 1;
        adj[u].push_back(v);
        id[{u, v}] = i;
    }

    if (!dfs()) return false;
    return true;
}

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