Submission #695311

#	Time	Username	Problem	Language	Result	Execution time	Memory
695311		79brue	Thousands Islands (IOI22_islands)	C++17	100 / 100	580 ms	51196 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;
multimap<pair<int, int>, int> edgeMap2;

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 = edgeMap2.find(make_pair(x, y));
        if(it != edgeMap2.end() && it->first == make_pair(x, y) &&
           (!(!ret.empty() && ret.back() == it->second) ||
            (next(it) != edgeMap2.end() && next(it)->first == make_pair(x, y)))){
            if(!ret.empty() && ret.back() == it->second) ++it;
            ret.push_back(it->second);
            edgeMap2.erase(it);
            edgeMap.insert(make_pair(make_pair(y, x), ret.back()));
        }
        else{
            it = edgeMap.find(make_pair(x, y));
            if(!ret.empty() && ret.back() == it->second) ++it;
            ret.push_back(it->second);
            edgeMap.erase(it);
            edgeMap2.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);
        int ns = *link[s].begin();
        link[s].erase(link[s].find(ns));
        revLink[ns].erase(revLink[ns].find(s));
        s = ns;
    }

    while(!que.empty()){
        int x = que.front(); que.pop();
        deg[x] = 0;
        if(x==s) return 1;
        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);
                int ns = *link[s].begin();
                link[s].erase(link[s].find(ns));
                revLink[ns].erase(revLink[ns].find(s));
                s = ns;
                if(removed[ns]) return 1;
            }
        }
    }

    if(removed[s]) return true;
    return false;
}

int A = -1, B = -1;
bool visited[100002];
bool visitedinA[100002];
bool search_mode = 0;
bool search_overlap = 0;

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

vector<int> rec;
bool findCycle(int x, int lead, vector<int> &path, vector<int> &cycle, bool ina=0){
    if(x==s) rec.clear();
    visited[x] = 1;
    rec.push_back(x);
    for(auto y: link[x]){
        if(x==s && y!=lead) continue;
        if(visited[y]){
            if(!ina || (y==0 && visitedinA[x]) || visitedinA[y]){
                int c = find(rec.begin(), rec.end(), y) - rec.begin();
                for(int i=0; i<=c; i++) path.push_back(rec[i]);
                for(int i=c+1; i<(int)rec.size(); i++) cycle.push_back(rec[i]);
                return true;
            }
            continue;
        }
        if(findCycle(y, lead, path, cycle, ina)) return true;
    }
    rec.pop_back();
    return false;
}

bool inCycle[100002];

vector<int> record;
bool findInCycle(int x, int lead, vector<int> &path){
    visited[x] = 1;
    record.push_back(x);

    for(auto y: link[x]){
        if(x==s && y!=lead) continue;
        if(inCycle[y] && y!=s){
            for(auto z: record){
                path.push_back(z);
            }
            path.push_back(y);
            return true;
        }
        if(visited[y]) continue;
        if(findInCycle(y, lead, path)) return true;
    }
    record.pop_back();
    return false;
}

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

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

    justSearch(s);

    /// Case 2. A=B
    if(A==B){
        vector<int> pathA, cycleA;
        memset(visited, 0, sizeof(visited));
        findCycle(s, A, pathA, cycleA);
        cycleA.insert(cycleA.begin(), pathA.back());
        pathA.pop_back();

        if(find(cycleA.begin(), cycleA.end(), s) == cycleA.end()){ /// 시작점이 포함되지 않음
            int c = cycleA[0];
            add(ret, startList);
            add(ret, pathA); add(ret, cycleA); ret.push_back(c); add(ret, pathA, 1); ret.pop_back();
            add(ret, pathA); ret.push_back(c); add(ret, cycleA, 1); add(ret, pathA, 1);
            add(ret, startList, 1);
            return ret;
        }
        else{
            add(ret, startList);
            add(ret, pathA); add(ret, cycleA);
            ret.push_back(s);

            int idx = find(cycleA.begin(), cycleA.end(), B) - cycleA.begin();
            for(int i=idx; i>=0; i--) ret.push_back(cycleA[i]);
            for(int i=(int)cycleA.size()-1; i>=idx; i--) ret.push_back(cycleA[i]);

            ret.push_back(s);
            add(ret, startList, 1);
            return ret;
        }
    }

    /// Case 1. A -> B의 경로가 없다
    if(!visitedinA[B] && !search_overlap){
        /// 각각 사이클 찾기
        vector<int> pathA, cycleA, pathB, cycleB;
        memset(visited, 0, sizeof(visited));
        findCycle(s, A, pathA, cycleA);
        memset(visited, 0, sizeof(visited));
        findCycle(s, 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 3. A->B의 경로가 있다
    vector<int> pathB, cycleB;
    memset(visited, 0, sizeof(visited));
    findCycle(s, B, pathB, cycleB, 1);

    cycleB.insert(cycleB.begin(), pathB.back());
    pathB.pop_back();

    if(find(cycleB.begin(), cycleB.end(), s) == cycleB.end()){ /// 시작점이 포함되지 않은 사이클
        for(auto x: cycleB) inCycle[x] = 1;

        add(ret, startList);
        add(ret, pathB);
        add(ret, cycleB);
        ret.push_back(cycleB[0]);
        add(ret, pathB, 1);

        vector<int> pathA;
        memset(visited, 0, sizeof(visited));
        findInCycle(s, A, pathA);

        int c = pathA.back();
        pathA.pop_back();

        ret.pop_back();
        add(ret, pathA);
        int idx = find(cycleB.begin(), cycleB.end(), c) - cycleB.begin();
        for(int i=idx; i>=0; i--) ret.push_back(cycleB[i]);
        for(int i=(int)cycleB.size()-1; i>=idx; i--) ret.push_back(cycleB[i]);
        add(ret, pathA, 1);
        add(ret, startList, 1);

        return ret;
    }

    /// 시작점이 포함된 사이클
    for(auto x: cycleB) inCycle[x] = 1;

    add(ret, startList);
    add(ret, cycleB);

    vector<int> pathA;
    memset(visited, 0, sizeof(visited));
    findInCycle(s, A, pathA);
    int c = pathA.back();
    pathA.pop_back();

    add(ret, pathA);
    int idx = find(cycleB.begin(), cycleB.end(), c) - cycleB.begin();
    for(int i=idx; i>=0; i--) ret.push_back(cycleB[i]);
    for(int i=(int)cycleB.size()-1; i>=idx; i--) ret.push_back(cycleB[i]);
    add(ret, pathA, 1);
    add(ret, startList, 1);

    return ret;
}

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