제출 #1183776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183776		gyg	수천개의 섬 (IOI22_islands)	C++20	8.40 / 100	65 ms	12616 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vec vector 
#define var variant
#define pii pair<int, int>
#define fir first 
#define sec second
const int N = 1e5 + 5;

int n, m;
arr<vec<int>, N> adj;
map<pii, int> id;

vec<int> stk, cyc;
arr<int, N> vs;
bool dfs(int u = 1) {
    vs[u] = 1, stk.push_back(u);
    for (int v : adj[u]) {
        if (vs[v] == 2) continue;
        if (vs[v] == 0)  {
            if (dfs(v)) return true;
            continue;
        }
        while (true) {
            int w = stk.back(); stk.pop_back();
            cyc.push_back(w);
            if (w == v) break;
        }
        stk.push_back(v);
        reverse(cyc.begin(), cyc.end());
        return true;
    }
    vs[u] = 2, stk.pop_back();
    return false;
}

vec<int> ap(vec<int> x, vec<int> y) {
    vec<int> ans = x;
    ans.insert(ans.end(), y.begin(), y.end());
    return ans;
}
vec<int> rv(vec<int> x) {
    vec<int> ans = x;
    reverse(ans.begin(), ans.end());
    return ans;
}
vec<int> op(vec<int> x) {
    vec<int> ans;
    for (int i : x) {
        if (i % 2 == 0) ans.push_back(i + 1);
        else ans.push_back(i - 1);
    }
    return ans;
}

var<bool, vec<int>> find_journey(int _n, int _m, vec<int> _u, vec<int> _v) {
    n = _n, m = _m;
    for (int i = 0; i < m; i++) {
        int u = _u[i] + 1, v = _v[i] + 1;
        adj[u].push_back(v);
        id[{u, v}] = i;
    }

    if (!dfs()) return false;

    if (stk.size() == 1 && cyc.size() == 2) {
        int u = cyc[0], v = cyc[1];
        int a = id[{u, v}], c = (a % 2 == 0) ? a + 1 : a - 1;
        int b = id[{v, u}], d = (b % 2 == 0) ? b + 1 : b - 1;
        vec<int> ans = {a, b, c, d, b, a, d, c};
        return ans;
    }

    // for (int u : stk) cout << u << " ";
    // cout << '\n';
    // for (int u : cyc) cout << u << " ";
    // cout << '\n';

    vec<int> x, y;
    for (int i = 0; i < stk.size(); i++)
        if (i + 1 != stk.size()) x.push_back(id[{stk[i], stk[i + 1]}]);
    for (int i = 0; i < cyc.size(); i++)
        y.push_back(id[{cyc[i], cyc[(i + 1) % cyc.size()]}]);
    

    vec<int> ans;
    
    ans = ap(ans, x);
    ans = ap(ans, y);
    ans = ap(ans, rv(x));
    
    ans = ap(ans, op(x));
    ans = ap(ans, rv(y));
    ans = ap(ans, rv(op(x)));

    return ans;
}

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