Submission #1228853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228853		ericl23302	Thousands Islands (IOI22_islands)	C++20	5 / 100	31 ms	24136 KiB

islands

#include "islands.h"

#include <bits/stdc++.h>

using namespace std;

pair<int, int> dfs(vector<bool> &visited, vector<int> &parents, vector<vector<int>> &adjacency1, vector<vector<int>> &adjacency2, int cur, int parent) {
    visited[cur] = true;
    parents[cur] = parent;
    if (!adjacency2[cur].empty()) return {cur, -1};
    for (int &child : adjacency1[cur]) {
        if (child == parent) continue;
        if (visited[child]) return {cur, child};
        auto curRes = dfs(visited, parents, adjacency1, adjacency2, child, cur);
        if (curRes.first != -1) return curRes;
    }

    return {-1, -1};
}

std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
    vector<vector<vector<int>>> adjacencyMatrix(N, vector<vector<int>>(N));
    vector<vector<int>> adjacency1(N), adjacency2(N);
    for (int i = 0; i < M; ++i) adjacencyMatrix[U[i]][V[i]].push_back(i);
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            if (adjacencyMatrix[i][j].size() == 1) adjacency1[i].push_back(j), adjacency1[j].push_back(i);
            else if (adjacencyMatrix[i][j].size() > 1) adjacency2[i].push_back(j), adjacency2[j].push_back(i);
        }
    }

    vector<bool> visited(N, false);
    vector<int> parents(N, -1);
    auto res = dfs(visited, parents, adjacency1, adjacency2, 0, -1);
    if (res.first == -1) return false;

    vector<int> journey, cycle;
    vector<bool> newVisited(N, false);
    int cur = res.first;
    while (cur != -1) {
        journey.push_back(cur);
        newVisited[cur] = true;
        cur = parents[cur];
    }
    reverse(journey.begin(), journey.end());

    if (res.second == -1) {
        cycle.push_back(res.first);
        cycle.push_back(adjacency2[res.first][0]);
    } else {
        vector<int> journey2;
        int cur2 = res.second;
        while (cur2 != -1) {
            if (newVisited[cur2]) break;
            journey2.push_back(cur2);
            cur2 = parents[cur2];
        }
        reverse(journey2.begin(), journey2.end());

        int i = 0;
        while (journey[i] != cur2) ++i;
        while (journey.size() > i) {
            cycle.push_back(journey.back());
            journey.pop_back();
        }
        journey.push_back(cur2);
        reverse(cycle.begin(), cycle.end());

        while (!journey2.empty()) {
            cycle.push_back(journey2.back());
            journey2.pop_back();
        }
    }

    // for (int &i : journey) cout << i << ' ';
    // cout << endl;

    vector<int> ans;
    int jSz = journey.size(), cSz = cycle.size();
    for (int i = 0; i < jSz - 1; ++i) ans.push_back(adjacencyMatrix[journey[i]][journey[i + 1]][0]);

    if (cSz == 2) {
        int a = cycle[0], b = cycle[1];
        ans.push_back(adjacencyMatrix[a][b][0]);
        ans.push_back(adjacencyMatrix[b][a][0]);
        ans.push_back(adjacencyMatrix[a][b][1]);
        ans.push_back(adjacencyMatrix[a][b][0]);
        ans.push_back(adjacencyMatrix[b][a][0]);
        ans.push_back(adjacencyMatrix[a][b][1]);
    } else {
        cycle.push_back(cycle[0]);
        vector<int> cycle2;
        for (int &i : cycle) cycle2.push_back(i);
        reverse(cycle2.begin(), cycle2.end());

        // for (int &i : cycle) cout << i << ' ';
        // cout << endl;
        // for (int &i : cycle2) cout << i << ' ';
        // cout << endl;

        cSz = cycle.size();

        for (int i = 0; i < cSz - 1; ++i) ans.push_back(adjacencyMatrix[cycle[i]][cycle[i + 1]][0]);
        for (int i = 0; i < cSz - 1; ++i) ans.push_back(adjacencyMatrix[cycle2[i]][cycle2[i + 1]][0]);
        for (int i = cSz - 2; i >= 0; --i) ans.push_back(adjacencyMatrix[cycle[i]][cycle[i + 1]][0]);
        for (int i = cSz - 2; i >= 0; --i) ans.push_back(adjacencyMatrix[cycle2[i]][cycle2[i + 1]][0]);
    }

    for (int i = jSz - 2; i >= 0; --i) ans.push_back(adjacencyMatrix[journey[i]][journey[i + 1]][0]);

    assert(ans.size() % 2 == 0);

    return ans;
}

// int main() 
// {
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);

//     srand(time({}));

//     int n = 1000;
//     int m = 100;

//     for (int _ = 0; _ < 100; ++_) {
//         vector<int> u, v;
//         vector<int> curIn = {0};
//         vector<bool> used(n, false);
//         used[0] = true;
//         for (int i = 0; i < m; ++i) {
//             int cur = 0;
//             while (used[cur]) cur = rand() % 1000;
//             int connect = rand() % (curIn.size());
//             u.push_back(cur); u.push_back(curIn[connect]);
//             v.push_back(curIn[connect]); v.push_back(cur);
//             used[cur] = true;
//             curIn.push_back(cur);
//         }

//         cout << "TEST: " << _ << endl;
//         for (int &i : u) cout << i << "   ";
//         cout << endl;
//         for (int &i : v) cout << i << "   ";
//         cout << endl;
    
//         auto res = find_journey(n, m, u, v);
//         if (res.index() == 1) {
//             cout << "ERROR: output is list" << endl;
//             vector<int> x = get<vector<int>>(res);
//             for (int &i : x) cout << i << ' ';
//             cout << endl;
//             break;
//         } else if (get<bool>(res) == true) {
//             cout << "ERROR: output is TRUE" << endl;
//         } else {
//             cout << "SUCCESS" << endl;
//         }
//     }

//     return 0;
// }

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