Submission #1207582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207582		garam1732	Thousands Islands (IOI22_islands)	C++17	55.15 / 100	182 ms	34284 KiB

islands

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

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 100100*1;
const ll MOD = 998244353;
const ll INF = 2e9;

queue<int> q;
set<pi> adj[MAXN], adjt[MAXN];
int chk[MAXN];

void clean() {
    while(q.size()) {
        int here = q.front(); q.pop();

        for(auto [there, x] : adj[here]) {
            adjt[there].erase(pi(here, x));
        } for(auto [there, x] : adjt[here]) {
            adj[there].erase(pi(here, x));
            if(adj[there].size() == 0) q.push(there);
        }

        adj[here].clear(); adjt[here].clear();
    }
}

vector<int> tmp, res;
vector<pi> pathA, cycleA, pathB, cycleB;
vector<int> A, B;
bool flag;
std::variant<bool, std::vector<int>> find_journey(
        int N, int M, std::vector<int> U, std::vector<int> V) {
    for(int i=0; i<M; i++) {
        adj[U[i]].insert(pi(V[i], i));
        adjt[V[i]].insert(pi(U[i], i));
    }

    for(int i=0; i<N; i++) {
        if(adj[i].empty()) q.push(i);
    } clean();

    // if 0 erased then return false
    if(adj[0].empty()) return false;

    int here = 0;
    while(true) {
        if(adj[here].empty()) return false;

        if(adj[here].size() == 1) {
            auto [there, x] = *adj[here].begin();
            q.push(here); clean();
            tmp.push_back(x); here = there; continue;
        }

        // first cycle
        chk[here] = 1;
        int there = adj[here].begin()->ff, x = adj[here].begin()->ss;
        pathA.push_back(pi(here, x));
        while(true) {
            if(chk[there]) {
                //for(auto [there,x]:pathA)cout<<x<<bl;cout<<endl;
                while(true) {
                    cycleA.push_back(*pathA.rbegin());
                    pathA.pop_back();

                    if(cycleA.rbegin()->ff == there) break;
                }
                break;
            }

            chk[there] = 1;
            pathA.push_back(pi(there, 0));
            x = adj[there].begin()->ss, there = adj[there].begin()->ff;
            pathA.rbegin()->ss = x;
        } reverse(all(cycleA));
        //for(auto [there,x]:cycleA) cout<<x<<bl;cout<<endl;

        // for(auto [there,x] : pathA) A.push_back(x);
        // for(auto [there,x] : cycleA) A.push_back(x);
        // reverse(all(pathA));
        // for(auto [there,x] : pathA) A.push_back(x);

        // second cycle
        memset(chk, 0, sizeof chk);
        for(auto [there,x] : cycleA) chk[there] = -1;

        chk[here] = 1;
        there = adj[here].rbegin()->ff, x = adj[here].rbegin()->ss;
        pathB.push_back(pi(here, x));
        while(true) {
            if(chk[there] == 1) {
                while(true) {
                    cycleB.push_back(*pathB.rbegin());
                    pathB.pop_back();

                    if(cycleB.rbegin()->ff == there) break;
                } reverse(all(cycleB));
                
                break;
            } else if(chk[there] == -1) {
                int j=0; flag = 1;
                while(cycleA[j].ff!=there) j++;

                int sz=cycleA.size();
                for(int k=0; k<sz; k++) {
                    j=(j-1+sz)%sz;
                    cycleB.push_back(cycleA[j]);
                }

                break;
            }

            chk[there] = 1;
            pathB.push_back(pi(there, 0));
            x = adj[there].begin()->ss, there = adj[there].begin()->ff;
            pathB.rbegin()->ss = x;
        }

        // for(auto [there,x] : pathB) B.push_back(x);
        // for(auto [there,x] : cycleB) B.push_back(x);
        // reverse(all(pathB));
        // for(auto [there,x] : pathB) B.push_back(x);

        break;
    }

    for(int x:tmp) res.push_back(x); reverse(all(tmp));
    int cnt = (flag ? 1 : 2);
    while(cnt--) {
        for(auto [there,x]:pathA) res.push_back(x); reverse(all(pathA));
        for(auto [there,x]:cycleA) res.push_back(x); reverse(all(cycleA));
        for(auto [there,x]:pathA) res.push_back(x);
        for(auto [there,x]:pathB) res.push_back(x); reverse(all(pathB));
        for(auto [there,x]:cycleB) res.push_back(x); reverse(all(cycleB));
        for(auto [there,x]:pathB) res.push_back(x);
    }
    for(int x:tmp) res.push_back(x);
    assert(res.size() <= 2000000);
    return res;
}

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