Submission #634761

#	Time	Username	Problem	Language	Result	Execution time	Memory
634761		JeanBombeur	Thousands Islands (IOI22_islands)	C++17	100 / 100	129 ms	23960 KiB

islands

#include "islands.h"
#include <variant>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

//  <|°_°|>

//  JeanBombeur & M. Broccoli

//  The hardest choices require the strongest wills

//  What is better - to be born good, or to overcome your evil nature with great effort ?

const int MAX_ISLANDS = (1e5);

vector <pair <int, int>> Adj[MAX_ISLANDS];
vector <int> Up[MAX_ISLANDS];

int nbIslands, nbCanoes;

vector <int> Path[3];

vector <int> Cycle[2];

vector <int> Ans;

int Seen[MAX_ISLANDS];

int Deg[MAX_ISLANDS];

int Queue[MAX_ISLANDS];
int deb = 0, fin = 0;

int Dfs(int node, int id, int root) {
    if (Seen[node])
        return node;
    Seen[node] = 1;
    for (pair <int, int> dest : Adj[node])
    {
        if (Seen[dest.first] >= 0)
        {
            Path[id].push_back(dest.second);
            int up = Dfs(dest.first, id, root);
            if (!id)
            {
                if (up >= 0)
                {
                    Cycle[id].push_back(dest.second);
                    Seen[node] = 2;
                    Path[id].pop_back();
                }
                else
                    Seen[node] = 0;
                if (node != root)
                    return up == node ? -1 : up;
            }
            if (up >= 0 && Seen[up] == 1)
            {
                Path[id].pop_back();
                Cycle[id].push_back(dest.second);
                if (node != root)
                    return up == node ? -1 : up;
            }
            if (node != root || id)
                return up;
            id ++;
        }
    }
    return -1;
}

void Add(vector <int> &a, int rev = 0) {
    if (rev)
        for (vector <int>::reverse_iterator it = a.rbegin(); it != a.rend(); it ++)
            Ans.push_back(*it);
    else
        for (vector <int>::iterator it = a.begin(); it != a.end(); it ++)
            Ans.push_back(*it);
    return;
}

int Clear() {
    for (int i = 0; i < nbIslands; i ++)
    {
        if (!Deg[i])
            Queue[fin ++] = i;
    }
    int start = 0;
    while (deb < fin || Deg[start] <= 1)
    {
        if (deb < fin)
        {
            int node = Queue[deb ++];
            Seen[node] = -1;
            for (int dest : Up[node])
                if (!(-- Deg[dest]))
                    Queue[fin ++] = dest;
        }
        while (Deg[start] <= 1)
        {
            pair <int, int> next = {-1, 0};
            Seen[start] = -1;
            Deg[start] = 0;
            for (int dest : Up[start])
                if (!(-- Deg[dest]))
                    Queue[fin ++] = dest;
            
            for (pair <int, int> dest : Adj[start])
                if (!Seen[dest.first])
                    next = dest;
            if (~next.first)
                start = next.first, Path[2].push_back(next.second);
            else
                return -1;
        }
    }
    return start;
}

variant <bool, vector <int>> find_journey(int N, int M, vector <int> Start, vector <int> End) {
    nbIslands = N, nbCanoes = M;
    for (int i = 0; i < nbCanoes; i ++)
    {
        Adj[Start[i]].push_back({End[i], i});
        Deg[Start[i]] ++;
        Up[End[i]].push_back(Start[i]);
    }

    int start = -1;
    if ((start = Clear()) < 0)
        return false;
    
    Dfs(start, 0, start);
    
    Add(Path[2]);
    Add(Path[0]);
    Add(Cycle[0], 1);
    Add(Path[0], 1);
    Add(Path[1]);
    
    if (Cycle[1].empty())
    {
        int node = End[Path[1].back()];
        int id = 0;
        int sz = Cycle[0].size();
        for (int i = 0; i < sz; i ++)
        {
            if (End[Cycle[0][i]] == node)
                id = i;
        }
        for (int i = id; i < sz; i ++)
            Ans.push_back(Cycle[0][i]);
        for (int i = 0; i < id; i ++)
            Ans.push_back(Cycle[0][i]);
    }
    else
        Add(Cycle[1], 1);
    Add(Path[1], 1);
    
    if (!Cycle[1].empty())
    {
        Add(Path[0]);
        Add(Cycle[0]);
        Add(Path[0], 1);
        Add(Path[1]);
        Add(Cycle[1]);
        Add(Path[1], 1);
    }
    Add(Path[2], 1);
    
    return Ans;
}

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