Submission #1024736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024736		Wansur	Thousands Islands (IOI22_islands)	C++17	26 / 100	59 ms	25252 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]];
        if(x == y){
            int l = -1, r = -1;
            for(int i:g[x]){
                if(v[i] == 0){
                    if(l == -1){
                        l = i;
                    }
                    else{
                        r = i;
                    }
                }
            }
            ans = {g[0][0], l, g[0][1], r, l, g[0][0], r, g[0][1]};
            return ans;
        }
        ans = {g[0][0], a[x][0], g[0][1], a[y][0], a[x][0], g[0][0], a[y][0], g[0][1]};
        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){
            continue;
        }
        if(l == -1){
            l = v[i];
        }
        else if(r == -1){
            r = v[i];
        }
    }
    if(r == -1) return false;
    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]};
    if(l == r){
        l = r = -1;
        for(int i:g[x]){
            if(v[i] == y){
                y = -1;
                continue;
            }
            if(l == -1){
                l = i;
            }
            else if(r == -1){
                r = i;
            }
        }
        int to = v[l], tl = -1, tr = -1;
        for(int i:g[to]){
            if(v[i] == x){
                if(tl == -1){
                    tl = i;
                }
                else{
                    tr = i;
                }
            }
        }
        t = {l, tl, r, tr, tl, l, tr, 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: 21 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 45