Submission #628674

#	Time	Username	Problem	Language	Result	Execution time	Memory
628674		qwerasdfzxcl	Thousands Islands (IOI22_islands)	C++17	100 / 100	339 ms	37784 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
pair<int, int> E[200200];
set<pair<int, int>> adj[100100], INV[100100];
vector<int> deg0, ansf, ansb;
int n, s, on[100100], visited[100100];
bool flag = 0;

vector<int> operator + (const vector<int> &a, const vector<int> &b){
    vector<int> ret = a;
    for (auto &x:b) ret.push_back(x);
    return ret;
}

vector<int> rev(vector<int> a){reverse(a.begin(), a.end()); return a;}

void pop(int x){
    auto [v, i] = *adj[x].begin();
    adj[x].erase(adj[x].begin());
    INV[v].erase(INV[v].find(make_pair(x, i)));
}

void _erase(int x){
    if (!on[x]) return;
    on[x] = 0;
    for (auto &[v, i]:INV[x]){
        adj[v].erase(adj[v].find(make_pair(x, i)));
        if (adj[v].empty()) deg0.push_back(v);
    }
    for (auto &[v, i]:adj[x]) INV[v].erase(INV[v].find(make_pair(x, i)));
}

void flip(int i){
    auto [u, v] = E[i];
    adj[u].erase(adj[u].find(make_pair(v, i))); INV[u].emplace(v, i);
    INV[v].erase(INV[v].find(make_pair(u, i))); adj[v].emplace(u, i);
}

vector<int> cyc;
vector<int> find_cycle(int x){
    auto iter = cyc.begin();
    for (;iter!=cyc.end();iter++) if (E[*iter].second == x) break;
    ++iter;
    return rev(vector<int>(iter, cyc.end()) + vector<int>(cyc.begin(), iter));
}

pair<vector<int>, vector<int>> solve(int is, int typ){ ///returns (path, cycle)
    int cur = E[is].second;
    vector<int> ret1 = {is};
    if (!visited[s]) visited[s] = typ;

    while(!visited[cur]){
        visited[cur] = typ;
        ret1.push_back(adj[cur].begin()->second);
        cur = adj[cur].begin()->first;
    }

    if (visited[cur]!=typ){ ///use same cycle
        flag = 1;
        return {ret1, find_cycle(cur)};
    }

    int tmp = cur==s?is:adj[cur].begin()->second;
    auto iter = find(ret1.begin(), ret1.end(), tmp);
    vector<int> ret2(iter, ret1.end());
    ret1.erase(iter, ret1.end());

    for (auto &x:ret1) visited[E[x].first] = 0;
    for (auto &x:ret2) flip(x);
    return {ret1, ret2};
}

std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {

    n = N, s = 1;
    fill(on+1, on+n+1, 1);
    for (int i=0;i<M;i++){
        ++U[i], ++V[i];
        adj[U[i]].emplace(V[i], i);
        INV[V[i]].emplace(U[i], i);
        E[i] = {U[i], V[i]};
    }

    for (int i=1;i<=n;i++) if (adj[i].empty()) deg0.push_back(i);
    while(true){
        while(!deg0.empty()){
            int x = deg0.back(); deg0.pop_back();
            _erase(x);
        }
        if (!on[s]) return false;
        if (adj[s].size()>1) break;

        ansf.push_back(adj[s].begin()->second);
        ansb.push_back(adj[s].begin()->second);
        int nxt = adj[s].begin()->first;
        _erase(s);
        s = nxt;
    }

    for (int i=1;i<=n;i++) if (on[i]){
        int sz = (i==s)?2:1;
        while((int)adj[i].size()>sz) pop(i);
    }

    int i1 = adj[s].begin()->second, i2 = adj[s].rbegin()->second;
    auto [p1, c1] = solve(i1, 1); cyc = c1;
    auto [p2, c2] = solve(i2, 2);

    if (flag) return ansf + p1 + c1 + rev(p1) + p2 + c2 + rev(p2) + rev(ansb);

    return ansf + p1 + c1 + rev(p1) + p2 + c2 + rev(p2) + p1 + rev(c1) + rev(p1) + p2 + rev(c2) + rev(p2) + rev(ansb);
}

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