Submission #1074410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074410		Zicrus	Thousands Islands (IOI22_islands)	C++17	9.10 / 100	33 ms	9540 KiB

islands

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

typedef long long ll;

int n, m;
vector<vector<pair<int, int>>> adj, revAdj; // edgeId, node
vector<bool> vst;
unordered_multiset<ll> has;

bool poss(int cur, int par) {
    if (vst[cur]) return false;
    vst[cur] = true;
    int cnt = 0;
    for (auto &e : adj[cur]) {
        ll hash = ((ll)min(cur, e.second) << 31) | max(cur, e.second);
        if (!has.count(hash)) continue;
        if (has.count(hash) == 1 && e.second == par) continue;
        if (poss(e.second, cur)) return true;
        cnt++;
    }
    return cnt >= 2;
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    n = N; m = M;
    adj = vector<vector<pair<int, int>>>(n);
    for (int i = 0; i < m; i++) {
        adj[U[i]].push_back({i, V[i]});
        if (U[i] < V[i]) {
            ll hash = ((ll)U[i] << 31) | V[i];
            has.insert(hash);
        }
    }
    vst = vector<bool>(n);
    return poss(0, -1);
}

#ifdef TEST
#include "grader.cpp"
#endif

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