Submission #1056795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056795		vjudge1	Thousands Islands (IOI22_islands)	C++17	1.75 / 100	22 ms	5232 KiB

islands

#include "islands.h"

#include <variant>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;

variant<bool, vi> find_journey(int n, int m, vi U, vi V) {
    vi InDeg(n, 0), OutDeg(n, 0);
    vector<vector<ii> > L(n);
    for(int i = 0; i < m; ++i) {
        L[U[i]].push_back({V[i], i});
        ++OutDeg[U[i]];
        ++InDeg[V[i]];
    }
    bool ok = false;
    vi viz(n, 0);
    stack<ii> S;
    vi Re;
    function<void(int, int, int)> dfs = [&](int u, int p, int parc) {
        if(ok) return;
        if(viz[u] == 2) return;
        if(viz[u] == 1) {
            vector<ii> Cic;
            while(!S.empty() && S.top().first!= u) {
                Cic.push_back(S.top());
                S.pop();
            }
            reverse(Cic.begin(), Cic.end());
            Cic.push_back({u, parc});
            vector<ii> Rest;
            while(!S.empty()) {
                Rest.push_back(S.top());
                S.pop();
            }
            vi Sol;
            reverse(Rest.begin(), Rest.end());
            for(auto it : Rest)
                Sol.push_back(it.second);
            for(auto it : Cic)
                Sol.push_back(it.second);
            for(auto it : Cic)
                Sol.push_back(it.second ^ 1);
            reverse(Cic.begin(), Cic.end());
            for(auto it : Cic)
                Sol.push_back(it.second);
            for(auto it : Cic)
                Sol.push_back(it.second ^ 1);
            reverse(Rest.begin(), Rest.end());
            for(auto it : Rest)
                Sol.push_back(it.second);
            Re = Sol;
            ok = 1;
            return;
        }
        if(parc != -1)
            S.push({u, parc});
        viz[u] = 1;
        int nrf = 0;
        vector<ii> Fii;
        for(auto [it, nrc] : L[u]) {
            if(it != p) {
                ++nrf;
                Fii.push_back({it, nrc});
            }
        }
        for(auto [it, nrc] : L[u]) {
            if(it != p) {
                dfs(it, u, nrc);
            }
        }
        viz[u] = 2;
    };
    dfs(0, -1, -1);
    if(ok && !Re.empty()) return Re;
    return ok;
}

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