Submission #1064029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064029		vjudge1	Thousands Islands (IOI22_islands)	C++17	24 / 100	74 ms	16312 KiB

islands

#include "islands.h"

#include <bits/stdc++.h>

using namespace std;

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


void validate(vi Sol, int n, int m, vi &U, vi &V) {
    int u = 0;
    vi stare(m, 0);
    assert(!Sol.empty());
    for(int i = 0; i + 1 < int(Sol.size()); ++i)
        assert(Sol[i] != Sol[i + 1]);
    for(auto it : Sol) {
        if(!stare[it]) {
            assert(u == U[it]);
        } else {
            assert(u == V[it]);
        }
        stare[it] ^= 1;
        assert(u == U[it] || u == V[it]);
        u = u ^ U[it] ^ V[it];
    }
    assert(u == 0);
    for(int i = 0; i < m; ++i)
        assert(!stare[i]);
}

variant<bool, vi> find_journey(int n, int m, vi U, vi V) {
    vector<set<int> > Smuchii(n), Smuchii2(n);
    vector<bool> activ(n, true);
    vi InDeg(n, 0), OutDeg(n, 0);
    for(int i = 0; i < m; ++i) {
        Smuchii[U[i]].insert(V[i]);
        Smuchii2[V[i]].insert(U[i]);
        ++OutDeg[U[i]];
        ++InDeg[V[i]];
    }
    set<int> DeSters;
    for(int i = 0; i < n; ++i) {
        if((!InDeg[i] && i != 0) || !OutDeg[i]) {
            DeSters.insert(i);
        }
    }
    while(!DeSters.empty()) {
        int u = *DeSters.begin();
        DeSters.erase(u);
        activ[u] = false;
        for(auto it : Smuchii[u]) {
            --InDeg[it];
            Smuchii2[it].erase(u);
            if(!InDeg[it] && activ[it]) {
                DeSters.insert(it);
            }
        }
        for(auto it : Smuchii2[u]) {
            --OutDeg[it];
            Smuchii[it].erase(u);
            if(!OutDeg[it] && activ[it]) {
                DeSters.insert(it);
            }
        }
    }
    if(!activ[0]) return false;
    ///am curatat graful
    vector<vector<ii> > L(n);
    for(int i = 0; i < m; ++i) {
        if(activ[U[i]] && activ[V[i]]) {
            L[U[i]].push_back({V[i], i});;
        }
    }

    vi S;
    vi viz(n, 0);

    vi Sol;
    bool ok = false;

    function<void(int, int)> dfs = [&](int u, int ultm) {
        if(ok) return;

        if(viz[u] == 2) return;
        if(viz[u] == 1) {
            vi Cyc;
            Cyc.push_back(S.back());
            S.pop_back();
            while(!S.empty() && V[S.back()] != u) {
                Cyc.push_back(S.back());
                S.pop_back();
            }
            vi S1 = S;

            for(auto it : S1) Sol.push_back(it);

            reverse(Cyc.begin(), Cyc.end());
            for(auto it : Cyc) Sol.push_back(it);
            for(auto it : Cyc) Sol.push_back(it ^ 1);
            reverse(Cyc.begin(), Cyc.end());
            for(auto it : Cyc) Sol.push_back(it);
            for(auto it : Cyc) Sol.push_back(it ^ 1);

            reverse(S1.begin(), S1.end());
            for(auto it : S1) Sol.push_back(it);

            ok = 1;
            return;
        }
        viz[u] = 1;
        for(auto [it, id] : L[u]) {
            if(id / 2 == ultm / 2) continue;
            S.push_back(id);
            dfs(it, id);
            if(ok) break;
            if(!S.empty() && S.back() == id) S.pop_back();
        }
        viz[u] = 2;
    };
    dfs(0, -2);
    if(Sol.empty()) return false;
    
    validate(Sol, n, m, U, V);
    
    return Sol;
}

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