Submission #710767

#	Time	Username	Problem	Language	Result	Execution time	Memory
710767		Jarif_Rahman	Thousands Islands (IOI22_islands)	C++17	100 / 100	536 ms	52356 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, m;
vector<int> U, V;
vector<vector<int>> initial_graph, initial_graph_r;
vector<bool> reachable;

vector<set<int>> in(n), out(n);
set<pair<int, int>> st;

void dfs_reachability(int nd){
    if(reachable[nd]) return;
    reachable[nd] = 1;
    for(int x: initial_graph[nd]) dfs_reachability(x);
}

void remove_node(int nd){
    st.erase({out[nd].size(), nd});

    for(int i: in[nd]){
        st.erase({out[U[i]].size(), U[i]});
        out[U[i]].erase(i);
        st.insert({out[U[i]].size(), U[i]});
    }
    for(int i: out[nd]) in[V[i]].erase(i);
    out[nd].clear();
    in[nd].clear();
}

void preprocess(){
    in.resize(n);
    out.resize(n);
    for(int i = 0; i < m; i++){
        if(!reachable[U[i]] || !reachable[V[i]]) continue;
        out[U[i]].insert(i);
        in[V[i]].insert(i);
    }

    for(int i = 0; i < n; i++){
        st.insert({out[i].size(), i});
    }

    while(!st.empty() && st.begin()->f == 0) remove_node(st.begin()->sc);
}

vector<int> path_from_0(int nd){
    vector<int> dis(n, -1);
    queue<int> Q;
    dis[0] = 0;
    Q.push(0);
    while(!Q.empty()){
        int nd = Q.front(); Q.pop();
        for(int x: initial_graph[nd]) if(dis[x] == -1){
            dis[x] = dis[nd]+1;
            Q.push(x);
        }
    }

    vector<int> path;
    while(nd != 0){
        for(int i: initial_graph_r[nd]) if(dis[U[i]] == dis[nd]-1){
            path.pb(i);
            nd = U[i];
            break;
        }
    }

    reverse(path.begin(), path.end());
    return path;
}

vector<bool> bl;
vector<int> cycle, to_cycle, cycle_nd;
bool found = 0;
void dfs(int nd, int i){
    if(found) return;
    if(bl[nd]){
        while(cycle_nd.back() != nd){
            cycle.pb(to_cycle.back());
            to_cycle.pop_back();
            cycle_nd.pop_back();
        }
        reverse(cycle.begin(), cycle.end());
        cycle.pb(i);
        found = 1;
        return;
    }
    bl[nd] = 1;
    to_cycle.pb(i);
    cycle_nd.pb(nd);

    for(int j: out[nd]) dfs(V[j], j);
    if(!found){
        to_cycle.pop_back();
        cycle_nd.pop_back();
    }
}

vector<int> path2;
vector<bool> cycle_bl;
void dfs2(int nd, int i){
    if(found) return;
    if(bl[nd]) return;
    bl[nd] = 1;

    path2.pb(i);
    if(cycle_bl[nd]){
        found = 1;
        return;
    }

    for(int j: out[nd]) dfs2(V[j], j);
    if(!found){
        path2.pop_back();
    }
}


variant<bool, vector<int>> find_journey(int _n, int _m, vector<int> _U, vector<int> _V){
    n = _n, m = _m, U = _U, V = _V;

    initial_graph.assign(n, {});
    initial_graph_r.assign(n, {});
    reachable.assign(n, 0);

    for(int i = 0; i < m; i++) initial_graph[U[i]].pb(V[i]), initial_graph_r[V[i]].pb(i);

    dfs_reachability(0);
    preprocess();

    set<int> cur = {0};

    int ND = -1;
    while(!cur.empty()){
        for(int x: cur){
            if(out[x].size() >= 2) ND = x;
        }
        if(ND != -1) break;
        set<int> _cur;
        for(int x: cur) for(int i: out[x]) _cur.insert(V[i]);
        for(int x: cur) remove_node(x);
        while(!st.empty() && st.begin()->f == 0) remove_node(st.begin()->sc);
        swap(cur, _cur);
    }


    if(ND == -1) return false;

    auto p1 = path_from_0(ND);

    found = 0, cycle = {}, to_cycle = {}, cycle_nd = {ND};
    bl.assign(n, 0);
    bl[ND] = 1;
    dfs(V[*out[ND].begin()], *out[ND].begin());
    auto p2 = to_cycle, c1 = cycle;

    cycle_bl.assign(n, 0);
    for(int i: c1) cycle_bl[U[i]] = 1, cycle_bl[V[i]] = 1;
    bl.assign(n, 0);
    found = 0;
    dfs2(V[*next(out[ND].begin())], *next(out[ND].begin()));

    vector<int> ans;

    if(found){
        ans.insert(ans.end(), p1.begin(), p1.end());
        ans.insert(ans.end(), p2.begin(), p2.end());
        ans.insert(ans.end(), c1.begin(), c1.end());
        ans.insert(ans.end(), p2.rbegin(), p2.rend());
        ans.insert(ans.end(), path2.begin(), path2.end());

        int k = -1;
        for(int i = 0; i < c1.size(); i++) if(V[c1[i]] == V[path2.back()]) k = i;
        for(int i = 0; i < c1.size(); i++) ans.pb(c1[int(int(k+c1.size())-i)%int(c1.size())]);

        ans.insert(ans.end(), path2.rbegin(), path2.rend());
        ans.insert(ans.end(), p1.rbegin(), p1.rend());
        return ans;
    }

    found = 0, cycle = {}, to_cycle = {}, cycle_nd = {ND};
    bl.assign(n, 0);
    bl[ND] = 1;
    dfs(V[*next(out[ND].begin())], *next(out[ND].begin()));
    auto p3 = to_cycle, c2 = cycle;

    ans.insert(ans.end(), p1.begin(), p1.end());
    ans.insert(ans.end(), p2.begin(), p2.end());
    ans.insert(ans.end(), c1.begin(), c1.end());
    ans.insert(ans.end(), p2.rbegin(), p2.rend());
    ans.insert(ans.end(), p3.begin(), p3.end());
    ans.insert(ans.end(), c2.begin(), c2.end());
    ans.insert(ans.end(), p3.rbegin(), p3.rend());
    ans.insert(ans.end(), p2.begin(), p2.end());
    ans.insert(ans.end(), c1.rbegin(), c1.rend());
    ans.insert(ans.end(), p2.rbegin(), p2.rend());
    ans.insert(ans.end(), p3.begin(), p3.end());
    ans.insert(ans.end(), c2.rbegin(), c2.rend());
    ans.insert(ans.end(), p3.rbegin(), p3.rend());
    ans.insert(ans.end(), p1.rbegin(), p1.rend());

    return ans;
}

Compilation message (stderr)

islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:180:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |         for(int i = 0; i < c1.size(); i++) if(V[c1[i]] == V[path2.back()]) k = i;
      |                        ~~^~~~~~~~~~~
islands.cpp:181:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |         for(int i = 0; i < c1.size(); i++) ans.pb(c1[int(int(k+c1.size())-i)%int(c1.size())]);
      |                        ~~^~~~~~~~~~~

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