Submission #694912

#	Time	Username	Problem	Language	Result	Execution time	Memory
694912		79brue	Thousands Islands (IOI22_islands)	C++17	11.90 / 100	59 ms	12444 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 removeUselessVertices(){
    /// outdegree 0 삭제
    queue<int> que;
    for(int i=0; i<n; i++){
        deg[i] = (int)link[i].size();
        if(!deg[i]) que.push(i);
    }
    if(deg[0] == 1) for(auto y: revLink[0]) que.push(y);

    while(!que.empty()){
        int x = que.front(); que.pop();
        removed[x] = 1;
        deg[x] = 0;
        for(auto y: revLink[x]){
            deg[y]--;
            if(!deg[y] && !removed[y]) que.push(y);
        }
    }

    if(removed[0]) 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