Submission #1024711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024711		Wansur	Thousands Islands (IOI22_islands)	C++17	12.35 / 100	93 ms	25356 KiB

islands

#include <bits/stdc++.h>
#include <variant>
#define f first
#define s second
#define ent '\n'

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 12;
const int mod = 1e9 + 2022;

map<int, int> a[maxn];
vector<int> g[maxn];
int n, m;

variant<bool, vector<int>> find_journey(int N, int M, vector<int> u, vector<int> v){
    n = N, m = M;
    for(int i=0;i<m;i++){
        a[u[i]][v[i]] = i;
        g[u[i]].push_back(i);
    }
    vector<int> ans;
    if(g[0].size() >= 2){
        int x = v[g[0][0]], y = v[g[0][1]];
        ans = {a[0][x], a[x][0], a[0][y], a[y][0], a[x][0], a[0][x], a[y][0], a[0][y]};
        return ans;
    }
    if(g[0].size() == 0) return false;
    int x = v[g[0][0]], sz = 1, y = 0;
    ans = {g[0][0]};
    while(g[x].size() == 2){
        int t = 0;
        if(v[g[x][t]] == y){
            t++;
        }
        ans.push_back(g[x][t]);
        y = x;
        x = v[g[x][t]];
        sz++;
    }
    if(g[x].size() <= 1) return false;
    int l = -1, r = -1;
    for(int i:g[x]){
        if(v[i] == y){
            y = -1;
            continue;
        }
        if(l == -1){
            l = v[i];
        }
        else if(r == -1){
            r = v[i];
        }
    }
    vector<int> t = {a[x][l], a[l][x], a[x][r], a[r][x], a[l][x], a[x][l], a[r][x], a[x][r]};
    for(int x:t){
        ans.push_back(x);
    }
    for(int i=sz-1;i>=0;i--){
        ans.push_back(ans[i]);
    }
    return ans;
}

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