Submission #1235542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235542		jasonic	Thousands Islands (IOI22_islands)	C++20	12.35 / 100	121 ms	13792 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
#include <variant>

using namespace std;

#define ll long long

variant<bool, std::vector<int>> find_journey(int n, int m, std::vector<int> u, std::vector<int> v) {
    vector<vector<int>> adjlist(n);
    map<pair<int, int>, int> edges;

    for(int i = 0; i < m; i++) {
        adjlist[u[i]].push_back(v[i]);
        edges[make_pair(u[i], v[i])] = i;
    }

    vector<int> parent(n, -1);
    vector<int> edgeUsed(n, -1);
    vector<bool> vis(n, false);
    queue<int> bfs;

    bfs.push(0);
    vis[0] = true;

    while(!bfs.empty()) {
        int curr = bfs.front(); bfs.pop();

        int one = -1, two = -1;
        for(auto i : adjlist[curr]) if(!vis[i]) {
            if(one == -1) one = i;
            else if(two == -1) {
                two = i;
                break;
            }
        }

        if(two != -1) {
            vector<int> order;
            vector<int> ans;

            int t1 = parent[curr];
            int t2 = curr;
            
            while(t2 != 0) {
                order.push_back(edges[make_pair(t1, t2)]);
                t1 = parent[t1];
                t2 = parent[t2];
            }

            reverse(order.begin(), order.end());

            for(auto i : order) ans.push_back(i);
            
            int e0to1, e1to0, e0to2, e2to0;
            e0to1 = edges[make_pair(curr, one)];
            e1to0 = edges[make_pair(one, curr)];
            e0to2 = edges[make_pair(curr, two)];
            e2to0 = edges[make_pair(two, curr)];

            vector<int> cancel({e0to1, e1to0, e0to2, e2to0, e1to0, e0to1, e2to0, e0to2});

            for(auto i : cancel) ans.push_back(i);

            reverse(order.begin(), order.end());
            for(auto i : order) ans.push_back(i);
            
            return ans;
        } else if(one != -1) {
            bfs.push(one);
            parent[one] = curr;
            vis[one] = true;
        }
    }

    return false;
}

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