제출 #1359466

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1359466		opeleklanos	수천개의 섬 (IOI22_islands)	C++20	0 / 100	17 ms	4124 KiB

islands

#include <iostream>
#include <vector>
#include <variant>
#include <algorithm>
using namespace std;

vector<vector<pair<int, int>>> adj;
vector<int> path;

vector<int> vis;
vector<int> tpsort;



void dfs(int st){
    vis[st] = 1;
    for(auto c : adj[st]) if(!vis[c.first]) dfs(c.first);

    tpsort.push_back(st);
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V){

    adj.assign(N, {});
    vis.assign(N, 0);

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

    dfs(0);

    reverse(tpsort.begin(), tpsort.end());
    vector<int> indx(N, -1);
    for(int i = 0; i<N; i++) indx[tpsort[i]] = i;

    for(int i = 0; i<N; i++){
        if(!vis[i]) continue;
        for(auto j : adj[i]){
            if(indx[i] > indx[j.first]) return (bool)1;
        }
    }

    return (bool)0;
}

• 서브태스크 1: 0 / 5
• 서브태스크 2: 0 / 5
• 서브태스크 3: 0 / 21
• 서브태스크 4: 0 / 24
• 서브태스크 5: 0 / 45