| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1242802 | Zbyszek99 | Thousands Islands (IOI22_islands) | C++20 | 0 ms | 0 KiB |
#include "islands.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
int out_deg[100001];
vi in_graph[100001];
bool del[100001];
vector<pii> out_graph[100001];
queue<int> events;
vi ans;
int beg_path_siz = 0;
bool odw[100001];
void del_vert(int x)
{
del[x] = 1;
forall(it,in_graph[x])
{
out_deg[it]--;
if(out_deg[it] == 0) events.push(it);
}
}
int new_beg(int v)
{
int v2 = -1;
forall(it,out_graph[v])
{
if(del[it.ff]) continue;
v2 = it.ff;
beg_path_siz++;
ans.pb(it.ss);
}
del_vert(v);
return v2;
}
vi find_cycle(int v, int beg, int n)
{
vi ans2;
rep(i,n) odw[i] = 0;
odw[beg] = 1;
while(odw[v] == 0)
{
ans2.pb(out_graph[v][0].ss);
odw[v] = 1;
v = out_graph[v][0].ff;
}
return ans2;
}
variant<bool,vi> find_journey(int n, int m, vi u, vi v)
vi find_journey(int n, int m, vi u, vi v)
{
rep(i,m)
{
out_graph[u[i]].pb({v[i],i});
}
rep(i,m)
{
out_deg[u[i]]++;
in_graph[v[i]].pb(u[i]);
}
rep(i,n)
{
if(out_deg[i] == 0) events.push(i);
}
int cur_beg = 0;
while(out_deg[cur_beg] <= 1)
{
int nb = new_beg(cur_beg);
if(nb == -1) return (bool)0;
cur_beg = nb;
}
while(!events.empty())
{
int x = events.front();
events.pop();
if(del[x]) continue;
del_vert(x);
while(out_deg[cur_beg] <= 1)
{
int nb = new_beg(cur_beg);
if(nb == -1) return (bool)0;
cur_beg = nb;
}
}
rep(i,n) out_graph[i] = {};
rep(i,m)
{
if(del[u[i]] || del[v[i]]) continue;
out_graph[u[i]].pb({v[i],i});
}
vi cycle1 = {out_graph[cur_beg][0].ss};
vi pom = find_cycle(out_graph[cur_beg][0].ff,cur_beg,n);
forall(it,pom) cycle1.pb(it);
cycle1.pb(out_graph[cur_beg][0].ss);
vi cycle2 = {out_graph[cur_beg][1].ss};
pom = find_cycle(out_graph[cur_beg][1].ff,cur_beg,n);
forall(it,pom) cycle2.pb(it);
cycle2.pb(out_graph[cur_beg][1].ss);
forall(it,cycle1) ans.pb(it);
forall(it,cycle2) ans.pb(it);
for(int i = beg_path_siz-1; i >= 0; i--)
{
ans.pb(ans[i]);
}
return ans;
}