제출 #630006

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
630006		Cauchico	수천개의 섬 (IOI22_islands)	C++17	11.90 / 100	307 ms	8916 KiB

islands

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

int n,m;
vector<vector<pair<int,int>>> adj,adj_rev;
vector<bool> used,valid,bused;
vector<int> order, component;

void dfs1(int v) {
    used[v] = true;

    for (auto u : adj[v])
        if (!used[u.first])
            dfs1(u.first);

    order.push_back(v);
}

void dfs2(int v) {
    used[v] = true;
    component.push_back(v);

    for (auto u : adj_rev[v])
        if (!used[u.first])
            dfs2(u.first);
}

bool dfs3(int v, int b) {
    bused[b] = true;
    if (valid[v]) {
        return true;
    }
    for (auto u: adj[v]) {
        if (!bused[u.second]) {
            if (dfs3(u.first,u.second)) {
                return true;
            }
        }
    }
    return false;
}

variant<bool,vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    n = N; m = M;
    adj.resize(n); adj_rev.resize(n); used.resize(n); valid.resize(n); bused.resize(m);

    for (int i=0;i<m;i++) {
        adj[U[i]].push_back({V[i],i});
        adj_rev[V[i]].push_back({U[i],i});
    }

    for (int i = 0; i < n; i++)
        if (!used[i])
            dfs1(i);

    used.assign(n, false);
    reverse(order.begin(), order.end());

    for (auto v : order) {
        if (!used[v]) {
            dfs2 (v);
            if (component.size() > 1) {
                for (auto k: component) {
                    valid[k] = true;
                }
            }
            component.clear();
        }
    }
    int cnt = 0;
    for (auto u: adj[0]) {
        cnt += dfs3(u.first,u.second);
    }
    if (cnt >= 2) {
        return true;
    } else {
        return false;
    }
    
}

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