Submission #1064345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064345		RaresFelix	Thousands Islands (IOI22_islands)	C++17	100 / 100	221 ms	37592 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]);
}

vi solve(int n, int s, vector<ii> &b, vector<ii> &ToGo) {
    ToGo[s] = b[0];
    
    vector<ii> S;
    vi viz(n, 0);
    int v = s;
    while(!viz[v]) {
        viz[v] = 1;
        auto [urm, id] = ToGo[v];
        assert(urm != -1);
        S.push_back(ToGo[v]);
        v = urm;
    }

    vi apartine_c0(n, 0);
    
    vi C0;
    apartine_c0[v] = 1;
    C0.push_back(S.back().second);
    S.pop_back();
    while(!S.empty() && S.back().first != v) {
        apartine_c0[S.back().first] = 1;
        C0.push_back(S.back().second);
        S.pop_back();
    }
    reverse(C0.begin(), C0.end());
    vi A0;
    for(auto [v_other, id] : S) A0.push_back(id);
    S.clear();
    viz.assign(n, 0);

    v = b[1].first;
    S.push_back(b[1]);
    while(!viz[v] && !apartine_c0[v]) {
        viz[v] = 1;
        auto [urm, id] = ToGo[v];
        assert(urm != -1);
        S.push_back(ToGo[v]);
        v = urm;
    }

    if(apartine_c0[v]) {
        ///ai ajuns in c0
        vi A1;
        for(auto [v_other, id] : S) A1.push_back(id);
        S.clear();
        vi C1;
        while(!viz[v]) {
            viz[v] = 1;
            auto [urm, id] = ToGo[v];
            assert(urm != -1);
            C1.push_back(id);
            v = urm;
        }

        vi Sol;
        copy(A0.begin(), A0.end(), back_inserter(Sol));
        copy(C0.begin(), C0.end(), back_inserter(Sol));
        copy(A0.rbegin(), A0.rend(), back_inserter(Sol));

        copy(A1.begin(), A1.end(), back_inserter(Sol));
        copy(C1.rbegin(), C1.rend(), back_inserter(Sol));
        copy(A1.rbegin(), A1.rend(), back_inserter(Sol));
        return Sol;
    }
    else {
        ///ai gasit un alt ciclu
        vi C1;
        C1.push_back(S.back().second);
        S.pop_back();
        while(!S.empty() && S.back().first != v) {
            apartine_c0[S.back().first] = 1;
            C1.push_back(S.back().second);
            S.pop_back();
        }
        vi A1;
        reverse(C1.begin(), C1.end());
        for(auto [v_other, id] : S) A1.push_back(id);
        S.clear();

        vi Sol;
        copy(A0.begin(), A0.end(), back_inserter(Sol));
        copy(C0.begin(), C0.end(), back_inserter(Sol));
        copy(A0.rbegin(), A0.rend(), back_inserter(Sol));

        copy(A1.begin(), A1.end(), back_inserter(Sol));
        copy(C1.begin(), C1.end(), back_inserter(Sol));
        copy(A1.rbegin(), A1.rend(), back_inserter(Sol));


        copy(A0.begin(), A0.end(), back_inserter(Sol));
        copy(C0.rbegin(), C0.rend(), back_inserter(Sol));
        copy(A0.rbegin(), A0.rend(), back_inserter(Sol));

        copy(A1.begin(), A1.end(), back_inserter(Sol));
        copy(C1.rbegin(), C1.rend(), back_inserter(Sol));
        copy(A1.rbegin(), A1.rend(), back_inserter(Sol));

        return Sol;
    }

}

variant<bool, vi> find_journey(int n, int m, vi U, vi V) {
    vector<set<ii> > 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], i});
        Smuchii2[V[i]].insert({U[i], 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);
        }
    }
    auto dezactiveaza = [&](int u) {
        DeSters.erase(u);
        activ[u] = false;
        for(auto [it, id] : Smuchii[u]) {
            --InDeg[it];
            Smuchii2[it].erase({u, id});
            if(!InDeg[it] && activ[it]) {
                DeSters.insert(it);
            }
        }
        for(auto [it, id] : Smuchii2[u]) {
            --OutDeg[it];
            Smuchii[it].erase({u, id});
            if(!OutDeg[it] && activ[it]) {
                DeSters.insert(it);
            }
        }
        Smuchii[u].clear();
        Smuchii2[u].clear();
        OutDeg[u] = InDeg[u] = 0;
    };
    int s = 0;
    while(!DeSters.empty()) {
        int u = *DeSters.begin();
        if(u == s && OutDeg[u]) {
            DeSters.erase(u);
            continue;
        }
        dezactiveaza(u);
    }
    if(!activ[0]) return false;
    vi Start;

    while(OutDeg[s] == 1) {
        activ[s] = 0;
        auto [ult, ultm] = *Smuchii[s].begin();
        --OutDeg[s];
        --InDeg[ult];
        dezactiveaza(s);
        s = ult;
        if(!activ[s]) return false;
        Start.push_back(ultm);

        while(!DeSters.empty()) {
            int u = *DeSters.begin();
            if(u == s && OutDeg[u]) {
                DeSters.erase(u);
                continue;
            }
            dezactiveaza(u);
        }
    }
    if(!activ[s] || OutDeg[s] < 2) return false;

    vector<ii> ToGo(n, ii{-1, -1});
    vector<ii> b;
    for(int i = 0; i < m; ++i) {
        int u = U[i], v = V[i];
        if(!activ[u] || !activ[v] || ToGo[u].second != -1)
            continue;
        if(u != s) {
            ToGo[u] = {v, i};
        } else {
            b.push_back({v, i});
        }
    }
    assert(b.size() == Smuchii[s].size());


    auto Sol0 = solve(n, s, b, ToGo);
    vi Sol;
    copy(Start.begin(), Start.end(), back_inserter(Sol));
    copy(Sol0.begin(), Sol0.end(), back_inserter(Sol));
    copy(Start.rbegin(), Start.rend(), back_inserter(Sol));
//    validate(Sol, n, m, U, V);
    return Sol;
}

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