제출 #1236511

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236511		Ghulam_Junaid	수천개의 섬 (IOI22_islands)	C++20	1.75 / 100	26 ms	16580 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 (1){        
        dead[start] = 1;
        int outd = 0, nxt = -1;

        for (int e : rev[start]){
            int u = U[e];
            out_deg[u]--;
            if (out_deg[u] == 0)
                dead[u] = 1;
        }

        for (int e : g[start]){
            int u = V[e];
            if (dead[u]) continue;
            outd++;
            nxt = u;
        }

        if (outd == 0) return false;
        if (outd > 1) return true;
        start = nxt;
        if (dead[start]) return false;
    }
    return true;
}

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