Submission #779816

#	Time	Username	Problem	Language	Result	Execution time	Memory
779816		GusterGoose27	Thousands Islands (IOI22_islands)	C++17	1.75 / 100	1105 ms	530676 KiB

islands

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5+5;
typedef pair<int, int> pii;

vector<pii> edges[MAXN];
vector<int> rev[MAXN];
bool dead[MAXN];
int deg[MAXN];
bool is_reversed[MAXN];
bool cyc[MAXN];
int vis[MAXN];
pii cnxt[MAXN];
pii cprv[MAXN];
int n, m;

void prune(int cur) {
    if (dead[cur] == 1) return;
    dead[cur] = 1;
    for (int prv: rev[cur]) {
        if (!dead[prv]) {
            deg[prv]--;
            if (deg[prv] == 0) prune(prv);
        }
    }
}

vector<int> stck;

pii find_cycle(int s, bool skip = 0) {
    vis[s] = 1;
    stck.push_back(s);
    for (pii p: edges[s]) {
        if (dead[p.first]) continue;
        if (skip) {
            skip = 0;
            continue;
        }
        cnxt[s] = p;
        if (vis[p.first] == 2) {
            vis[s] = 2;
            return p;
        }
        cprv[p.first] = pii(s, p.second);
        if (vis[p.first] == 1) {
            while (stck.back() != p.first) {
                cyc[stck.back()] = 1;
                stck.pop_back();
            }
            cyc[p.first] = 1;
            vis[s] = 2;
            return p;
        }
        find_cycle(p.first);
        vis[s] = 2;
        return p;
    }
    assert(false);
}

void get_cyc(int s, vector<int> &v) {
    if (!cyc[s]) {
        v.push_back(cnxt[s].second);
        get_cyc(cnxt[s].first, v);
        v.push_back(cnxt[s].second);
        return;
    }
    int t = s;
    do {
        int orig = t;
        if (is_reversed[t]) {
            v.push_back(cprv[t].second);
            t = cprv[t].first;
        }
        else {
            v.push_back(cnxt[t].second);
            t = cnxt[t].first;
        }
        is_reversed[orig] ^= 1;
    } while (t != s);
    return;
}

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++) {
        edges[U[i]].push_back(pii(V[i], i));
        rev[V[i]].push_back(U[i]);
        deg[U[i]]++;
    }
    for (int i = 0; i < n; i++) if (deg[V[i]] == 0) prune(V[i]);
    if (dead[0]) return false;
    int s = 0;
    vector<int> res;
    vector<int> s_edges;
    while (deg[s] <= 1) {
        if (dead[s]) return false;
        prune(s);
        deg[s] = 0;
        for (pii nxt: edges[s]) {
            if (!dead[nxt.first]) {
                res.push_back(nxt.second);
                s_edges.push_back(nxt.second);
                s = nxt.first;
                break;
            }
        }
    }
    assert(deg[s] >= 2);
    pii e1 = find_cycle(s);
    stck.clear();
    pii e2 = find_cycle(s, 1);
    res.push_back(e1.second);
    get_cyc(e1.first, res);
    res.push_back(e1.second);
    res.push_back(e2.second);
    get_cyc(e2.first, res);
    res.push_back(e2.second);
    res.push_back(e1.second);
    get_cyc(e1.first, res);
    res.push_back(e1.second);
    res.push_back(e2.second);
    get_cyc(e2.first, res);
    res.push_back(e2.second);
    for (int v: s_edges) res.push_back(v);
    return res;
}

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