Submission #694923

#	Time	Username	Problem	Language	Result	Execution time	Memory
694923		79brue	Thousands Islands (IOI22_islands)	C++17	35 / 100	329 ms	34660 KiB

islands

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

using namespace std;

typedef long long ll;

int n, m;
multiset<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]].insert(V[i]);
        revLink[V[i]].insert(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]) removed[i] = 1, que.push(i);
    }
    while(deg[s] == 1){
        for(auto y: revLink[s]){
            link[y].erase(link[y].find(s));
            deg[y]--;
            if(!deg[y] && !removed[y]) removed[y] = 1, que.push(y);
        }
        revLink[s].clear();
        startList.push_back(s);
        s = *link[s].begin();
    }

    while(!que.empty()){
        int x = que.front(); que.pop();
        deg[x] = 0;
        for(auto y: revLink[x]){
            deg[y]--;
            link[y].erase(link[y].find(x));

            if(!deg[y] && !removed[y]) removed[y] = 1, que.push(y);
            while(deg[s] == 1){
                for(auto y: revLink[s]){
                    link[y].erase(link[y].find(s));
                    deg[y]--;
                    if(!deg[y] && !removed[y]) removed[y] = 1, que.push(y);
                }
                revLink[s].clear();
                startList.push_back(s);
                s = *link[s].begin();
            }
        }
    }

    if(removed[s]) return true;

    return false;
}

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