| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1240999 | nikulid | Thousands Islands (IOI22_islands) | C++20 | 0 ms | 0 KiB |
#include "islands.h"
#include <map>
#include <variant>
#include <vector>
#include <algorithm>
#include <iostream>
bool debug=0;
#define derr if(debug)cerr
using namespace std;
#define pb push_back
#define mp make_pair
// below are used to find the trip itself (path in terms of nodes)
vector<vector<int>> adj(1000);
vector<bool> visitted(1000, 0), been(1000, 0);
vector<int> goes(1000, -1), from(1000, -1);
int cycle_found=0, cyclefrom=0;
bool found_a_cycle=false;
// below are used to find the canoes to do the trip (path in terms of canoes)
vector<vector<int>> adja(1000, vector<int>(1000, -1));
vector<vector<int>> adjb(1000, vector<int>(1000, -1));
void dfs(int node){
if(cycle_found)return;
derr<<"dfsing "<<node<<"...\n";
been[node]=1;
visitted[node]=1;
for(int i=0; i<adj[node].size(); i++){
if(!been[adj[node][i]]){
// un-explored node...
goes[node] = adj[node][i];
from[adj[node][i]] = node;
dfs(adj[node][i]);
} else if(been[adj[node][i]] && visitted[adj[node][i]]){
// cycle found!!!
cycle_found = adj[node][i];
found_a_cycle=true;
goes[node] = adj[node][i];
//from[adj[node][i]] = node;
cyclefrom = node;
return;
}
// otherwise, we have
// been[]=1 && visitted[]=0
// which means we've exhausted all options with this node already.
}
visitted[node]=0;
return;
}
variant<bool, vector<int>> find_journey(int n, int m, vector<int> u, vector<int> v) {
/*
adj[u] = {..., v, ...}
adja[u][v] = first canoe for u->v
adjb[u][v] = second canoe for u->v
( trip[i] = {node to travel to, 0(a)/1(b)/2(reverse,a)/3(reverse,b)}
*/
int u,v;
for(int i=0; i<m; i++){
u=u[i]; v=v[i];
if(adja[u][v] == -1){
adj[u].pb(v);
adja[u][v] = i;
} else{
adjb[u][v] = i;
}
}
dfs(0);
if(!found_a_cycle)derr<<"no cycle found :(\n";
if(debug)
{
cerr<<"<--- adj --->\n";
for(int i=0; i<n; i++){
cerr<<i<<": ";
for(int l=0; l<adj[i].size(); l++){
cerr<<adj[i][l]<<",";
}cerr<<"\n";
}
cerr<<"cyclefrom: "<<cyclefrom<<"\n";
cerr<<"goes: ";
for(int i=0; i<n; i++){
cerr<<goes[i]<<" ";
}
cerr<<"\nfrom: ";
for(int i=0; i<n; i++){
cerr<<from[i]<<" ";
}cerr<<"\n\n";
}
if(found_a_cycle){
derr<<"cycle found @ "<<cycle_found<<"!\n";
// now to find the canoes... (easy part? right? right???)
vector<int> answer;
// 0 -> cycle_found
derr<<"cycle 0...\n";
int cur=0;
while(cur != cycle_found){
answer.pb(adja[cur][goes[cur]]);
cur = goes[cur];
}
derr<<"cycle 1...\n";
// cycle_found -> cycle_found (forwards) x2
answer.pb(adja[cur][goes[cur]]);
cur = goes[cur];
while(cur != cycle_found){
answer.pb(adja[cur][goes[cur]]);
cur = goes[cur];
}
answer.pb(adjb[cur][goes[cur]]);
cur = goes[cur];
while(cur != cycle_found){
answer.pb(adjb[cur][goes[cur]]);
cur = goes[cur];
}
derr<<"cycle 2... (cur="<<cur<<")\n";
// cycle_found <- cycle_found (backwards) x2
//
//
//
answer.pb(adja[cyclefrom][cur]);
cur = cyclefrom;
derr<<"next cur: "<<cur<<"\n";
while(cur != cycle_found){
answer.pb(adja[from[cur]][cur]);
cur = from[cur];
}
answer.pb(adjb[cyclefrom][cur]);
cur = cyclefrom;
while(cur != cycle_found){
answer.pb(adjb[from[cur]][cur]);
cur = from[cur];
}
derr<<"cycle 3...\n";
// 0 <- cycle_found (backwards)
while(cur != 0){
answer.pb(adja[from[cur]][cur]);
cur = from[cur];
}
return answer;
}
else return false;
}