Submission #779840

#	Time	Username	Problem	Language	Result	Execution time	Memory
779840		GusterGoose27	Thousands Islands (IOI22_islands)	C++17	100 / 100	119 ms	23084 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];
bool cnt[2*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] = max(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[i] == 0) prune(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;
            }
        }
    }
    // return vector<int>();
    assert(deg[s] >= 2);
    pii e1 = find_cycle(s);
    stck.clear();
    pii e2 = find_cycle(s, 1);
    cnxt[s] = e1;
    get_cyc(s, res);
    res.push_back(e2.second);
    get_cyc(e2.first, res);
    res.push_back(e2.second);
    get_cyc(s, res);
    res.push_back(e2.second);
    get_cyc(e2.first, res);
    res.push_back(e2.second);
    reverse(s_edges.begin(), s_edges.end());
    for (int v: s_edges) res.push_back(v);
    int pos = 0;
    for (int v: res) {
        if (cnt[v] == 0) {
            assert(pos == U[v]);
            pos = V[v];
        }
        else {
            assert(pos == V[v]);
            pos = U[v];
        }
        cnt[v] ^= 1;
    }
    for (int i = 0; i < m; i++) assert(!cnt[i]);
    assert(res.size() < 2e6);
    for (int i = 0; i < res.size()-1; i++) assert(res[i] != res[i+1]);
    assert(!res.empty());
    return res;
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:143:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for (int i = 0; i < res.size()-1; i++) assert(res[i] != res[i+1]);
      |                     ~~^~~~~~~~~~~~~~

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