Submission #1057598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057598		vjudge1	Thousands Islands (IOI22_islands)	C++17	27.75 / 100	48 ms	16360 KiB

islands

#include "islands.h"

#include <bits/stdc++.h>
using namespace std;
set<pair<int,int>>adj[100100];
vector<int>RES;
bitset<100100>vis;
int dfs(int n){
    vis[n]=1;
    if(adj[n].size()>=2){
        auto[go,ind]=*adj[n].begin();
        auto[go2,ind2]=*++adj[n].begin();
        RES.push_back(ind);
        RES.push_back(ind^1);
        RES.push_back(ind2);
        RES.push_back(ind2^1);
        RES.push_back(ind^1);
        RES.push_back(ind);
        RES.push_back(ind2^1);
        RES.push_back(ind2);
        return 1;
    }
    for(auto[go,ind]:adj[n]){
        if(vis[go])continue;
        adj[go].erase({n,ind^1});
        RES.push_back(ind);
        if(dfs(go)) {
            RES.push_back(ind);
            return 1;
        }
        RES.pop_back();
    }
    return 0;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    if(N==2) {
        vector<int>atob,btoa;
        for(int i=0;i<M;i++)
            (U[i]?btoa:atob).push_back(i);
        if(atob.size()<2||btoa.empty())
            return false;
        vector<int>v;
        v.push_back(atob[0]);
        v.push_back(btoa[0]);
        v.push_back(atob[1]);
        v.push_back(atob[0]);
        v.push_back(btoa[0]);
        v.push_back(atob[1]);
        return v;
    } else {
        for(int i=0;i<M;i++)
            adj[U[i]].insert({V[i],i});
        if(dfs(0))
            return RES;
        return false;
    }
}

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