Submission #1235927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235927		Ghulam_Junaid	수천개의 섬 (IOI22_islands)	C++20	10.15 / 100	30 ms	17224 KiB

islands

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

const int N = 2e5 + 10;
int n, m, out_deg[N], dead[N];
vector<int> g[N], rev[N], U, V;

variant<bool, vector<int>> find_journey(int N, int M, vector<int> uu, vector<int> vv) {
    V = vv, U = uu;
    n = N, m = M;
    for (int i = 0; i < m; i ++){
        g[U[i]].push_back(i);
        out_deg[U[i]]++;
        rev[V[i]].push_back(i);
    }

    queue<int> q;
    for (int i = 0; i < n; i ++)
        if (!out_deg[i])
            q.push(i);

    while (!q.empty()){
        int v = q.front();
        q.pop();
        dead[v] = 1;

        for (int e : rev[v]){
            int u = U[e];
            out_deg[u]--;
            if (!out_deg[u])
                q.push(u);
        }
    }
    if (dead[0]) return false;

    for (int v = 0; v < n; v ++){
        vector<int> adj;
        for (int e : g[v]){
            int u = V[e];
            if (!dead[u] and !dead[v]) adj.push_back(e);
        }
        g[v] = adj;

        adj.clear();
        for (int e : rev[v]){
            int u = U[e];
            if (!dead[u] and !dead[v]) adj.push_back(e);
        }
        rev[v] = adj;
    }

    int start = 0;
    while (out_deg[start] == 1){
        int e = g[start][0];
        int nxt = V[e];
        start = nxt;
        if (start == 0) break;
    }

    if (out_deg[start] <= 1) return false;
    return true;
}

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