제출 #948157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
948157		Nhoksocqt1	수천개의 섬 (IOI22_islands)	C++17	13.40 / 100	189 ms	17492 KiB

islands

#ifndef Nhoksocqt1
    #include "islands.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;

vector<ii> adj[MAXN];
map<ii, int> cntEdge;
ii edge[2 * MAXN];
int low[MAXN], num[MAXN], tr[MAXN], numNode, numEdge;
bool dx[MAXN], dxt[2 * MAXN];

int getCntEdge(ii p) {
    return (cntEdge.find(p) != cntEdge.end()) ? cntEdge[p] : 0;
}

void dfs(int u, int lastID = -1) {
    dx[u] = 1;
    tr[u] = lastID;
    for (int it = 0; it < sz(adj[u]); ++it) {
        int v(adj[u][it].fi), id(adj[u][it].se);
        if(!dx[v])
            dfs(v, id);
    }
}

stack<int> st;
bool tarjan(int u) {
    st.push(u);
    low[u] = num[u] = ++num[numNode];

    for (int it = 0; it < sz(adj[u]); ++it) {
        int v(adj[u][it].fi), id(adj[u][it].se);
        if(!dxt[id]) {
            dxt[id] = 1;
            if(!num[v]) {
                if(tarjan(v))
                    return true;

                low[u] = min(low[u], low[v]);
            } else {
                low[u] = min(low[u], num[v]);
            }
        }
    }

    if(low[u] == num[u]) {
        int v, cnt(0);
        do {
            v = st.top(); st.pop();
            low[v] = num[v] = 1e9+7;
            ++cnt;
        } while(v != u);
        return (cnt > 2);
    }

    return false;
}

#ifdef Nhoksocqt1
    vector<int>
#else
    variant<bool, vector<int>>
#endif // Nhoksocqt1
    find_journey(int _N, int _M, vector<int> _U, vector<int> _V) {
    numNode = _N, numEdge = _M;
    for (int i = 0; i < numEdge; ++i) {
        int u(_U[i]), v(_V[i]);
        edge[i] = {u, v};
        ++cntEdge[ii(u, v)];
    }

    for (int i = 0; i < numEdge; ++i) {
        int u(edge[i].fi), v(edge[i].se);
        if(getCntEdge(ii(u, v)) > 1)
            adj[u].push_back(ii(v, i));
    }

    dfs(0);
    int x(-1), y(-1), z(-1);
    for (int i = 0; i < numNode; ++i) {
        if(dx[i]) {
            int t1(-1);
            for (int it = 0; it < sz(adj[i]); ++it) {
                int j(adj[i][it].fi);

                if(edge[tr[i]].fi != j && getCntEdge(ii(j, i)) > 0) {
                    if(t1 < 0) {
                        t1 = j;
                    } else
                        if(t1 != j) {
                            x = i, y = t1, z = j;
                            break;
                        }
                }
            }

            if(y >= 0)
                break;
        }
    }

    if(z >= 0) {
        int idx_y(-1), idy_x(-1), idx_z(-1), idz_x(-1);
        for (int i = 0; i < numEdge; ++i) {
            int u(edge[i].fi), v(edge[i].se);
            if(u == x && v == y)
                idx_y = i;

            if(u == y && v == x)
                idy_x = i;

            if(u == x && v == z)
                idx_z = i;

            if(u == z && v == x)
                idz_x = i;
        }

        vector<int> ans, pf;
        int u(x);
        while(u != 0) {
            ans.push_back(tr[u]);
            u = edge[tr[u]].fi;
        }

        pf = ans;
        reverse(ans.begin(), ans.end());

        vector<int> p({idx_y, idy_x, idx_z, idz_x, idy_x, idx_y, idz_x, idx_z});
        for (int it = 0; it < sz(p); ++it)
            ans.push_back(p[it]);

        for (int it = 0; it < sz(pf); ++it)
            ans.push_back(pf[it]);

        return ans;
    }

    for (int i = 0; i < numNode; ++i) {
        if(!dx[i])
            continue;

        for (int it = 0; it < sz(adj[i]); ++it) {
            int j(adj[i][it].fi);
            if(edge[tr[i]].fi != j && getCntEdge(ii(i, j)) > 1 && getCntEdge(ii(j, i)) > 0) {
                x = i, y = j;
                break;
            }
        }

        if(y >= 0)
            break;
    }

    if(y >= 0) {
        int idx_y_1(-1), idy_x(-1), idx_y_2(-1);
        for (int i = 0; i < numEdge; ++i) {
            int u(edge[i].fi), v(edge[i].se);
            if(u == x && v == y) {
                if(idx_y_1 < 0) {
                    idx_y_1 = i;
                } else {
                    idx_y_2 = i;
                }
            }

            if(u == y && v == x)
                idy_x = i;
        }

        vector<int> ans, pf;
        int u(x);
        while(u != 0) {
            ans.push_back(tr[u]);
            u = edge[tr[u]].fi;
        }

        pf = ans;
        reverse(ans.begin(), ans.end());

        vector<int> p({idx_y_1, idy_x, idx_y_2, idx_y_1, idy_x, idx_y_2});
        for (int it = 0; it < sz(p); ++it)
            ans.push_back(p[it]);

        for (int it = 0; it < sz(pf); ++it)
            ans.push_back(pf[it]);

        return ans;
    }

    for (int i = 0; i <= numNode; ++i)
        low[i] = num[i] = 0;

    if(tarjan(0))
        return true;

    #ifdef Nhoksocqt1
        return {-1};
    #else
        return false;
    #endif // Nhoksocqt1
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "islands"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    vector<int> _U, _V;
    int _N, _M;
    cin >> _N >> _M;

    _U.resize(_M), _V.resize(_M);
    for (int i = 0; i < _M; ++i)
        cin >> _U[i] >> _V[i];

    vector<int> p = find_journey(_N, _M, _U, _V);
    cout << "ANSWER: ";
    if(sz(p) == 1 && p[0] == -1) {
        cout << "NO\n";
    } else {
        for (int it = 0; it < sz(p); ++it)
            cout << p[it] << ' ';

        cout << '\n';
    }

    return 0;
}

#endif // Nhoksocqt1

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