Submission #1043674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043674		ProtonDecay314	Thousands Islands (IOI22_islands)	C++17	100 / 100	74 ms	19764 KiB

islands

#include "islands.h"

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

pair<vb, pair<vi, int>> remove_zero_outdeg(int n, int m, const vvpi& adj, const vvpi& adjt) {
    vb removed(n, false);

    vi outdeg(n, 0);

    queue<int> s;
    for(int i = 0; i < n; i++) {
        outdeg[i] = adj[i].size();

        if(outdeg[i] == 0) s.push(i);
    }

    vi tail_inds;
    int x = 0;

    do {
        while(!s.empty()) {
            int i = s.front();

            s.pop();

            if(removed[i]) continue;
            removed[i] = true;

            for(auto [j, _] : adjt[i]) {
                outdeg[j]--;

                if(outdeg[j] == 0) s.push(j);
            }
        }

        while(outdeg[x] == 1) {
            // Remove x
            int orig_x = x;
            bool found = false;
            for(auto [j, ci] : adj[x]) {
                if(!removed[j]) {
                    tail_inds.pb(ci);
                    x = j;
                    found = true;
                    break;
                }
            }

            if(found) {
                for(auto [j, _] : adjt[orig_x]) {
                    outdeg[j]--;

                    if(outdeg[j] == 0) s.push(j);
                }
                removed[orig_x] = true;
            }
        }
    } while(!s.empty());

    pair<vi, int> tail_info = {tail_inds, x};

    return {removed, tail_info};
}

// returns gng^-1
vi conjugate(const vi& g, const vi& n) {
    int gs = g.size(), ns = n.size();

    vi res;

    for(int i = 0; i < gs; i++) {
        res.pb(g[i]);
    }

    for(int i = 0; i < ns; i++) {
        res.pb(n[i]);
    }

    for(int i = gs - 1; i >= 0; i--) {
        res.pb(g[i]);
    }

    return res;
}

vi invert_path(const vi& path) {
    vi res;
    for(int i = path.size() - 1; i >= 0; i--) {
        res.pb(path[i]);
    }

    return res;
}

vi chain_paths(const vi& p1, const vi& p2) {
    vi res = p1;
    int p2s = p2.size();
    for(int i = 0; i < p2s; i++) {
        res.pb(p2[i]);
    }

    return res;
}

pair<vi, vi> find_cycle(int s, int n, int start_edge_ind, const vvpi& adj) {
    vb vis(n, false);

    int cur = s;
    // vis[cur] = true;
    // cur = adj[cur][start_edge_ind].fi;

    while(!vis[adj[cur][0].fi]) {
        vis[cur] = true;
        cur = adj[cur][0].fi;
    }
    int loop_n = adj[cur][0].fi;

    vi tail;
    vi cyc;

    cur = s;

    if(cur != loop_n) {
        // tail.pb(adj[cur][start_edge_ind].se);
        // cur = adj[cur][start_edge_ind].fi;
        while(cur != loop_n) {
            tail.pb(adj[cur][0].se);
            cur = adj[cur][0].fi;
        }
    }

    do {
        cyc.pb(adj[cur][0].se);
        cur = adj[cur][0].fi;
    } while(cur != loop_n);

    return {tail, cyc};
}

// vi shift_cycle(const vi& cyc, int sn, const vi& v) {
//     int cycs = cyc.size();

//     int start_ind = -1;

//     for(int i = 0; i < cycs; i++) {
//         if(v[cyc[i]] == sn) {
//             start_ind = i;
//             break;
//         }
//     }

//     start_ind++;
//     start_ind %= cycs;

//     vi res(cycs, 0);

//     for(int i = 0; i < cycs; i++) {
//         res[i] = cyc[(i + start_ind) % cycs];
//     }

//     return res;
// }

bool is_distinct(const vi& l1, const vi& l2) {
    int l1s = l1.size(), l2s = l2.size();

    int l1p = 0, l2p = 0;

    while(l1p < l1s && l2p < l2s) {
        if(l1[l1p] < l2[l2p]) l1p++;
        else if(l1[l1p] > l2[l2p]) l2p++;
        else return false;
    }
    return true;
}

bool is_reachable(const vi& path, vi u, vi v) {
    int ps = path.size();
    
    for(int i = 0; i < ps - 1; i++) {
        int temp = u[path[i]];
        u[path[i]] = v[path[i]];
        v[path[i]] = temp;
        if(u[path[i]] != u[path[i + 1]]) return false;
    }
    return true;
}

variant<bool, vi> find_journey(int n, int m, vi u, vi v) {
    vvpi adj;
    vvpi adjt;
    for(int i = 0; i < n; i++) {
        vpi adjr;
        vpi adjtr;
        adj.pb(adjr);
        adjt.pb(adjtr);
    }

    for(int i = 0; i < m; i++) {
        adj[u[i]].pb({v[i], i});
        adjt[v[i]].pb({u[i], i});
    }

    // Remove zero outdeg

    auto [to_remove, tail] = remove_zero_outdeg(n, m, adj, adjt);

    auto [g, x] = tail;

    if(to_remove[x]) {
        return false; // If island x is removed, it's impossible
    }

    // compute tail
    

    // Update adj
    for(int i = 0; i < n; i++) {
        adj[i].clear();
        adjt[i].clear();
    }

    for(int i = 0; i < m; i++) {
        if(to_remove[u[i]] || to_remove[v[i]]) continue;
        adj[u[i]].pb({v[i], i});
        adjt[v[i]].pb({u[i], i});
    }

    // Start from 0, find a node with outdegree >= 2. Call it X
    // Start from X, use canoe 1 and proceed until you cycle. Take note of the nodes in the cycle
    // Start from X, use canoe 2 and proceed until you cycle. Take note of the nodes in the cycle

    // If you can't find such a node, conclude that it is impossible

    if(adj[x].size() <= 1) {
        // cout << "WHOOPS " << x << endl;
        return false;
    }

    // CASE 1: If the cycle EDGES intersect at any point, replace one of the cycles with the other.
    // It doesn't matter which, just use the same cycle
    // g n1 cycle n1inv n2 cycleinv n2inv ginv

    // CASE 2: the cycles are EDGE-disjoint
    // g n1 cycle1 n1inv n2 cycle2 n2inv n1 cycle1inv n1inv n2 cycle2inv n2inv ginv

    int n1_scanoe = adj[x][0].se, n2_scanoe = adj[x][1].se;
    int n1_sn = adj[x][0].fi, n2_sn = adj[x][1].fi;

    auto [n1tail, n1cyc] = find_cycle(x, n, 0, adj);
    auto [n2tail, n2cyc] = find_cycle(n2_sn, n, 0, adj);

    // int n1_scycn = (n1tail.size() == 0 ? n1_sn : v[n1tail.back()]);
    // int n2_scycn = (n2tail.size() == 0 ? n2_sn : v[n2tail.back()]);
    reverse(n2tail.begin(), n2tail.end());
    n2tail.pb(n2_scanoe);
    reverse(n2tail.begin(), n2tail.end());

    vi n1cycs = n1cyc, n2cycs = n2cyc;
    sort(n1cycs.begin(), n1cycs.end());
    sort(n2cycs.begin(), n2cycs.end());


    // for(int& v : n1tail) cout << v << " ";
    // cout << "\n";
    // for(int& v : n1cyc) cout << v << " ";
    // cout << "\n";
    // for(int& v : n2tail) cout << v << " ";
    // cout << "\n";
    // for(int& v : n2cyc) cout << v << " ";
    // cout << "\n";

    // check if distinct
    vi ans;

    if(is_distinct(n1cycs, n2cycs)) {
        // The cycles are edge-disjoint, case 2
        // g n1 cycle1 n1inv n2 cycle2 n2inv n1 cycle1inv n1inv n2 cycle2inv n2inv ginv

        vi cyc_forward = chain_paths(conjugate(n1tail, n1cyc), conjugate(n2tail, n2cyc));
        vi cyc_backward = chain_paths(conjugate(n1tail, invert_path(n1cyc)), conjugate(n2tail, invert_path(n2cyc)));

        ans = conjugate(g, chain_paths(cyc_forward, cyc_backward));
    } else {
        // The cycles are NOT edge-disjoint, case 1
        // g n1 cycle n1inv n2 cycleinv n2inv ginv

        ans = conjugate(g, chain_paths(conjugate(n1tail, n1cyc), conjugate(n2tail, invert_path(n2cyc))));
    }

    // ! NOTE: it may help to have a utility function for "shifting" a cycle to start at some arbitrary node
    // It may also help to have a utility "reverse" function.
    // This is rather simple actually, just get a list of canoes and reverse it
    // It might not be necessary

    // bool has_rep = false;

    // int ans_sz = ans.size();

    // for(int i = 0; i < ans_sz - 1; i++) {
    //     if(ans[i] == ans[i + 1]) {
    //         has_rep = true;
    //         break;
    //     }
    // }

    // if(has_rep) return false;

    // if(!is_reachable(ans, u, v)) return false;

    return ans;
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, vi, vi)':
islands.cpp:272:9: warning: unused variable 'n1_scanoe' [-Wunused-variable]
  272 |     int n1_scanoe = adj[x][0].se, n2_scanoe = adj[x][1].se;
      |         ^~~~~~~~~
islands.cpp:273:9: warning: unused variable 'n1_sn' [-Wunused-variable]
  273 |     int n1_sn = adj[x][0].fi, n2_sn = adj[x][1].fi;
      |         ^~~~~

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