제출 #694918

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
694918		79brue	수천개의 섬 (IOI22_islands)	C++17	11.90 / 100	49 ms	10920 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
vector<int> link[100002], revLink[100002];

bool removeUselessVertices();

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

    if(removeUselessVertices()) return false;
    return true;
}

int deg[100002];
bool removed[100002];
bool seenAsStart[100002];
int s = 0;
vector<int> startList;

bool removeUselessVertices(){
    /// outdegree 0 삭제
    queue<int> que;
    for(int i=0; i<n; i++){
        deg[i] = (int)link[i].size();
        if(!deg[i]) removed[i] = 1, que.push(i);
    }
    if(deg[s] == 1) for(auto y: revLink[0]) removed[y] = 1, que.push(y);

    while(!que.empty()){
        int x = que.front(); que.pop();
        deg[x] = 0;
        for(auto y: revLink[x]){
            deg[y]--;
            if(!deg[y] && !removed[y]) removed[y] = 1, que.push(y);
            if(deg[s] == 1 && !seenAsStart[s]){
                seenAsStart[s] = 1;
                for(auto y: revLink[s]) que.push(y);
                startList.push_back(s);
                for(auto ns : link[s]) if(!removed[ns]) {s = ns; break;}
            }
        }
    }

    if(removed[s]) return true;

    for(int i=0; i<n; i++){
        vector<int> v;
        for(auto x: link[i]) if(!removed[x]) v.push_back(x);
        v.swap(link[i]);
    }

    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