Submission #633903

#	Time	Username	Problem	Language	Result	Execution time	Memory
633903		Cauchico	Thousands Islands (IOI22_islands)	C++17	9.10 / 100	33 ms	5296 KiB

islands

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

vector<vector<pair<int,int>>> adj;
vector<int> path,cycle; 
vector<bool> used;

void dfs(int v, int e) {
    used[v] = true;
    if (adj[v].size() > 2) {
        int p1,p2;
        if (adj[v][0].first == e) {
            p1 = adj[v][1].second;
            p2 = adj[v][2].second;
        }else if (adj[v][1].first == e) {
            p1 = adj[v][0].second;
            p2 = adj[v][2].second;
        }else {
            p1 = adj[v][0].second;
            p2 = adj[v][1].second;
        }
        int b1=p1^1,b2=p2^1;
        cycle = {p1,b1,p2,b2,b1,p1,b2,p2};
        return;
    }
    for (auto u: adj[v]) {
        if (!used[u.first]) {
            path.push_back(u.second);
            dfs(u.first,v);
        }
    }
}

variant<bool,vector<int>> find_journey( int n, int m, vector<int> u, vector<int> v) {
    adj.resize(n); used.resize(n);
    for (int i=0;i<m;i++) {
        adj[u[i]].push_back({v[i],i});
    }
    if (adj[0].size() > 1) {
        int p1 = adj[0][0].second; int b1 = p1^1;
        int p2 = adj[0][1].second; int b2 = p2^1;
        vector<int> ans = {p1,b1,p2,b2,b1,p1,b2,p1};
        return ans;
    } else {
        dfs(0,-1);
        if (cycle.size() == 0) {
            return false;
        }
        vector<int> ans;
        ans.insert(ans.end(),path.begin(),path.end());
        ans.insert(ans.end(),cycle.begin(),cycle.end());
        reverse(path.begin(),path.end());
        ans.insert(ans.end(),path.begin(),path.end());
        return ans;
    }
}

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