Submission #633200

#	Time	Username	Problem	Language	Result	Execution time	Memory
633200		tutis	Thousands Islands (IOI22_islands)	C++17	9.10 / 100	40 ms	5296 KiB

islands

#include "islands.h"

#include <variant>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    vector<int> C(N, 0);
    vector<int>b[N];
    vector<int>ff[N];
    for (int i = 0; i < M; i++)
    {
        C[U[i]]++;
        b[V[i]].push_back(U[i]);
        ff[U[i]].push_back(i);
    }
    int s = 0;
    vector<bool> e(N, true);
    stack<int>Q;
    for (int i = 0; i < N; i++)
        if (C[i] == 0)
            Q.push(i);
    vector<int>ans0;
    while (e[s])
    {
        if (C[s] == 1)
        {
            int s_ = -1;
            for (int ee : ff[s])
            {
                if (e[V[ee]])
                {
                    ans0.push_back(ee);
                    s_ = V[ee];
                }
            }
            for (int t : b[s])
            {
                if (e[t])
                {
                    C[t]--;
                    if (C[t] == 0)
                        Q.push(t);
                }
            }
            e[s] = false;
            s = s_;
            continue;
        }
        if (Q.empty())
            break;
        int a = Q.top();
        Q.pop();
        if (!e[a])
            continue;
        e[a] = false;
        for (int t : b[s])
        {
            if (e[t])
            {
                C[t]--;
                if (C[t] == 0)
                    Q.push(t);
            }
        }
    }
    if (!e[s])
        return false;
    return true;
}

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