Submission #694933

#	Time	Username	Problem	Language	Result	Execution time	Memory
694933		79brue	Thousands Islands (IOI22_islands)	C++17	0 / 100	15 ms	20460 KiB

islands

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

using namespace std;

typedef long long ll;

void add(vector<int> &A, vector<int> &B, int rev = 0){
    if(!rev) for(auto x: B) A.push_back(x);
    else for(int i=(int)B.size()-1; i>=0; i--) A.push_back(B[i]);
}

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

bool removeUselessVertices();
vector<int> solve();

multimap<pair<int, int>, int> edgeMap;

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;
    vector<int> ret;
    vector<int> ans = solve();
    for(int i=0; i<m; i++) edgeMap.insert(make_pair(make_pair(U[i], V[i]), i));

    for(int i=0; i<(int)ans.size()-1; i++){
        int x = ans[i], y = ans[i+1];
        auto it = edgeMap.find(make_pair(x, y));
        ret.push_back(it->second);
        edgeMap.erase(it);
        edgeMap.insert(make_pair(make_pair(y, x), ret.back()));
    }

    return ret;
}

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;
}

int A = -1, B = -1;
bool visited[100002];

void justSearch(int x){
    visited[x] = 1;
    for(auto y: link[x]){
        if(x==s && y!=A) continue;
        if(visited[y]) continue;
        justSearch(y);
    }
}

void findCycle(int x, int lead, vector<int> &path, vector<int> &cycle){
    vector<int> record;
    while(!visited[x]){
        visited[x] = 1;
        record.push_back(x);
        if(x == 0) x = lead;
        else x = *link[x].begin();
    }
    int c = find(record.begin(), record.end(), x) - record.begin();
    for(int i=0; i<=c; i++) path.push_back(record[i]);
    for(int i=c+1; i<(int)record.size(); i++) cycle.push_back(record[i]);
}

vector<int> solve(){
    vector<int> ret;

    assert((int)link[s].size() > 1);
    A = *link[s].begin();
    B = *next(link[s].begin());

    justSearch(0);

    /// Case 1. A -> B의 경로가 없다
    if(!visited[B]){
        /// 각각 사이클 찾기
        vector<int> pathA, cycleA, pathB, cycleB;
        memset(visited, 0, sizeof(visited));
        findCycle(0, A, pathA, cycleA);
        memset(visited, 0, sizeof(visited));
        findCycle(0, B, pathB, cycleB);

        add(ret, startList);

        add(ret, pathA);
        add(ret, cycleA);
        add(ret, pathA, 1);
        ret.pop_back();

        add(ret, pathB);
        add(ret, cycleB);
        add(ret, pathB, 1);
        ret.pop_back();

        add(ret, pathA);
        add(ret, cycleA, 1);
        add(ret, pathA, 1);
        ret.pop_back();

        add(ret, pathB);
        add(ret, cycleB, 1);
        add(ret, pathB, 1);

        add(ret, startList, 1);
        return ret;
    }

    /// Case 2. A->B의 경로가 있다
    vector<int> pathB, cycleB;
    findCycle(0, B, pathB, cycleB);

//    if(cycleB.find(s) == cycleB.end()){ /// 시작점이 포함되지 않은 사이클
//        cycleB.insert(cycleB.begin(), pathB.end());
//        pathB.pop_back();
//
//        ret.push_back();
//    }

    return vector<int> (1);
}

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