제출 #774520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
774520		GusterGoose27	수천개의 섬 (IOI22_islands)	C++17	0 / 100	41 ms	25172 KiB

islands

#include "islands.h"

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5;
vector<pii> edges[MAXN];
vector<pii> redges[MAXN];
bool dead[MAXN];
int outdeg[MAXN];
pii edge_list[MAXN];
int n, m;
vector<int> path;
bool vis[MAXN];
bool fin[MAXN];

void prune(int i) {
    dead[i] = 1;
    for (pii e: redges[i]) {
        if (dead[e.first]) continue;
        outdeg[e.first]--;
        if (outdeg[e.first] == 0) prune(e.first);
    }
}


pii nxt[MAXN];
pii prv[MAXN];
pii prv2[MAXN];
int pinch[MAXN];

void make_path(int cur, vector<int> &cpath, bool spec = 0) {
    if (spec) {
        make_path(prv2[cur].first, cpath);
        cpath.push_back(prv2[cur].second);
        return;
    }
    if (cur == 0) return;
    make_path(prv[cur].first, cpath);
    cpath.push_back(prv[cur].second);
}

set<int> cyc_less;
// set<int> all_prev;

int pinch_f;

bool dfs(int cur) {
    vis[cur] = 1;
    if (pinch[cur] == -1) cyc_less.insert(cur);
    // all_prev.insert(cur);
    for (pii e: edges[cur]) {
        if (dead[e.first]) continue;
        if (pinch[e.first] != -1) {
            int abssfae = 0;
            while (nxt[pinch[e.first]].first == -1) abssfae++;
            if (!fin[nxt[pinch[e.first]].first]) continue;
            // make_path(cur, path);
            path.push_back(e.second);
            pinch_f = pinch[e.first];
            return 1;
        }
        if (fin[e.first]) continue;
        if (vis[e.first]) {
            for (int v: cyc_less) {
                pinch[v] = e.first;
            }
            cyc_less.clear();
            prv2[pinch[cur]] = e;
            nxt[cur] = e;
            continue;
        }
        prv[e.first] = pii(cur, e.second);
        if (pinch[cur] == -1) nxt[cur] = e;
        if (dfs(e.first)) return 1;
    }
    if (cyc_less.find(cur) != cyc_less.end()) cyc_less.erase(cur);
    // all_prev.erase(cur);
    fin[cur] = 1;
    return 0;
}

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));
        redges[V[i]].push_back(pii(U[i], i));
        edge_list[i] = pii(U[i], V[i]);
        outdeg[U[i]]++;
    }
    for (int i = 0; i < n; i++) {
        if (!dead[i] && outdeg[i] == 0) prune(i);
    }
    if (dead[0]) return false;
    fill(pinch, pinch+n, -1);
    if (!dfs(0)) return false;
    return vector<int>({});
}

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