Submission #1211897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211897		Saul0906	Thousands Islands (IOI22_islands)	C++20	11.90 / 100	42 ms	13384 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repa(a,b) for(auto a:b)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define pb push_back

using namespace std;
using vi = vector<int>;

const int N=1e5+5;

bool vis[N];
vector<pii> adj[N], radj[N];

variant<bool, vi> find_journey(int n, int m, vi U, vi V) {
	int odg[n]{};
	rep(i,0,m){
		odg[U[i]]++;
		adj[U[i]].pb({V[i],i});
		radj[V[i]].pb({U[i],i});
	}
	vi bfcycle, cycle, afcycle, ans;
	int u=-1, s=0;
	while(odg[s]==1){
		vis[s]=true;
		bfcycle.pb(adj[s][0].se);
		afcycle.pb(adj[s][0].se);
		if(vis[adj[s][0].fi]) break;
		u=s;
		s=adj[s][0].fi;
	}
	queue<int> q;
	if(u!=-1) q.push(u), vis[u]=true;
	rep(i,0,n) if(!odg[i]) q.push(i), vis[i]=true;
	while(q.size()){
		u=q.front();
		q.pop();
		vis[u]=true;
		repa(v,radj[u]){
			odg[v.fi]--;
			assert(odg[v.fi]>=0);
			if(!odg[v.fi] && !vis[v.fi]) q.push(v.fi), vis[v.fi]=true;
		}
	}
	fill(vis,vis+n,0);
	rep(i,0,n) adj[i].clear(), radj[i].clear();
	if(odg[s]<2) return false;
	return true;
	reverse(all(afcycle));
	repa(e,bfcycle) ans.pb(e);
	repa(e,cycle) ans.pb(e);
	repa(e,afcycle) ans.pb(e);
	return ans;
}

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