Submission #652920

#	Time	Username	Problem	Language	Result	Execution time	Memory
652920		Lobo	Thousands Islands (IOI22_islands)	C++17	0 / 100	27 ms	43476 KiB

islands

#include "islands.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fr first
#define sc second
#define mp make_pair
#define all(x) x.begin(),x.end()

const int maxn = 2e5+10;
int n, m, tin[maxn], low[maxn], mark[maxn], iscyc[maxn], can0[maxn], timer, rec[maxn];
int dp[maxn], endcyc[maxn], markedg[maxn], atv[maxn];
int Ug[maxn], Vg[maxn];
vector<int> g[maxn], gt[maxn];
vector<pair<int,int>> gid[maxn], gaux[maxn];
map<int,vector<int>> boats[maxn];
map<int,int> boat[maxn];
vector<int> cur, final;

int cycid[maxn], cntcyc;
vector<int> path, cycord[maxn];
bool ans = 0;
void dfs(int u) {
    cout << " " << u << endl;
    mark[u] = 1;
    vector<int> vecids;
    for(auto V : gid[u]) {
        if(cycid[V.sc]) {
            vecids.pb(V.sc);
        }
    }
    if(vecids.size() > 1) {
        ans = 1;
        return;
    }

    for(auto id : vecids) {
        id = vecids[0];
        int v = Vg[id];
        markedg[id] = 1;
        if(mark[v]) {
            if(cycid[id]) {
                endcyc[cycid[id]] = v;
                // cout << "    " << v << " " << cycid[id] << endl;
            }
        }
        else {
            if(cycid[id] != 0) atv[cycid[id]] = 1;
            dfs(v);
            if(cycid[id] && endcyc[cycid[id]] == u) {
                // mark everyone in this cycle as an cycle
                for(auto x : cycord[cycid[id]]) iscyc[Ug[x]]++;
            }
        }

        if(iscyc[v] || dp[v]) {
            dp[u]++;
        }
    }

    for(auto V : gid[u]) {
        int v = V.fr;
        int id = V.sc;
        if(markedg[id]) continue;

        if(mark[v]) {
            if(cycid[id]) {
                endcyc[cycid[id]] = v;
                // cout << " " << cycid[id] << " " << v << endl;
            }
        }
        else {
            if(cycid[id] != 0) atv[cycid[id]] = 1;
            dfs(v);
            if(cycid[id] && endcyc[cycid[id]] == u) {
                // mark everyone in this cycle as an cycle
                for(auto x : cycord[cycid[id]]) iscyc[Ug[x]]++;
            }
        }

        if(iscyc[v] || dp[v]) {
            dp[u]++;
        }
    }

    // cout << u << " =  " << dp[u] << " " << iscyc[u] << endl;
    if(dp[u] >= 2) {
        ans = 1;
    }
}

void cycledecomp(int u) {
    rec[u] = 1;
    if(gaux[u].size()) {
        int v = gaux[u].back().fr;
        int id = gaux[u].back().sc;
        gaux[u].pop_back();
        if(rec[v]) {
            // I found a cycle
            cycid[id] = ++cntcyc;
            cycord[cntcyc].pb(id);
            while(path.size() && Vg[path.back()] != v) {
                int x = path.back(); path.pop_back();
                cycord[cntcyc].pb(x);
                cycid[x] = cntcyc;
            }
            reverse(all(cycord[cntcyc]));
        }
        else {
            path.pb(id);
            cycledecomp(v);
        }
    }
    rec[u] = 0;
}

void dfs0(int u) {
    can0[u] = 1;
    for(auto v : g[u]) {
        if(can0[v] == 0) dfs0(v);
    }
}


variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    n = N;
    m = M;
    for(int i = 0; i < m; i++) {
        Ug[i] = U[i];
        Vg[i] = V[i];
        g[U[i]].pb(V[i]);
        gid[U[i]].pb(mp(V[i],i));
        gt[V[i]].pb(U[i]);
        gaux[U[i]].pb(mp(V[i],i));
        boat[U[i]][V[i]] = i;
        boats[U[i]][V[i]].pb(i);
    }

    for(int i = 0; i < n; i++) {
        while(gaux[i].size()) cycledecomp(i);
    }

    for(int i = 0; i < n; i++) {
        for(int j = 1; j < gid[i].size(); j++) {
            if(cycid[gid[i][j].sc]) swap(gid[i][0],gid[i][j]);
        }
        for(int j = 2; j < gid[i].size(); j++) {
            if(cycid[gid[i][j].sc]) swap(gid[i][1],gid[i][j]);
        }
    }

    // for(int i = 0; i < m; i++) {
    //     cout << Ug[i] << " " << Vg[i] << " " << cycid[i] << endl;
    // }

    // for(int i = 1; i <= cntcyc; i++) {
    //     cout << Ug[cycord[i][0]] << " ";
    //     for(auto x : cycord[i]) {
    //         cout << Vg[x] << " ";
    //     }cout << endl;
    // }

    dfs(0);
    if(ans) {
        return final;
    }
    return false;

}

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:144:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         for(int j = 1; j < gid[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~
islands.cpp:147:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         for(int j = 2; j < gid[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~

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