Submission #1070353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070353		Unforgettablepl	Thousands Islands (IOI22_islands)	C++17	22.75 / 100	22 ms	6232 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;

variant<bool, vector<int>> find_journey(int N,int M,vector<int> U,vector<int> V){
    vector<vector<pair<int,int>>> adj(N);
    for(int i=0;i<M;i++){
        adj[U[i]].emplace_back(V[i],i);
    }
    vector<bool> visited(N);
    stack<int> path;
    vector<int> ans;
    vector<int> direction;
    function<int(int,int)> dfs = [&](int x,int pedge) {
        if(visited[x]) {
            return x;
        }
        visited[x]=true;
        bool found = false;
        pair<int,int> idxes = {-1,-1};
        for(auto&[v,idx]:adj[x])if(pedge!=idx) {
            path.emplace(idx);
            auto temp = dfs(v,idx^1);
            if(temp==-1){
                path.pop();
                if(found) {
                    idxes.second=idx;
                    break;
                }
                idxes.first=idx;
                found=true;
                continue;
            }
            if(temp==-2) {
                direction.emplace_back(idx);
                return -2;
            }
            ans.emplace_back(idx);
            if(temp!=x) {
                return temp;
            }
            reverse(ans.begin(), ans.end());
            vector<int> myans = ans;
            reverse(ans.begin(), ans.end());
            for(int&i:ans)myans.emplace_back(i^1);
            for(int&i:ans)myans.emplace_back(i);
            reverse(ans.begin(), ans.end());
            for(int&i:ans)myans.emplace_back(i^1);
            ans = myans;
            return -2;
        }
        if(idxes.second!=-1) {
            int a = idxes.first;
            int b = idxes.second;
            ans = {a,a^1,b,b^1,a^1,a,b^1,b};
            return -2;
        }
        return -1;
    };
    auto temp = dfs(0,-1);
    if(temp==-1)return false;
    reverse(direction.begin(), direction.end());
    vector<int> myans = direction;
    for(int&i:ans)myans.emplace_back(i);
    reverse(direction.begin(), direction.end());
    for(int&i:direction)myans.emplace_back(i);
    return myans;
}

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