Submission #1062037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062037		AdamGS	Thousands Islands (IOI22_islands)	C++17	35 / 100	65 ms	18260 KiB

islands

#include "islands.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
vector<int>V[LIM], S[LIM], cykl1, cykl2;
int deg[LIM], odw[LIM], czy[LIM], n, m, akt;
bool DFS(int x) {
	if(odw[x]) return false;
	odw[x]=1;
	for(auto i : V[x]) {
		if(i==akt) {
			cykl1.pb(x);
			return true;
		}
		if(DFS(i)) {
			cykl1.pb(x);
			return true;
		}
	}
	return false;
}
bool DFS2(int x) {
	if(!odw[x]) return false;
	odw[x]=1;
	if(czy[x]) {
		cykl2.pb(x);
		return true;
	}
	for(auto i : V[x]) if(DFS(i)) {
		cykl2.pb(x);
		return true;
	}
	return false;
}
variant<bool,vector<int>>find_journey(int _n, int _m, vector<int>_u, vector<int>_v) {
	n=_n; m=_m;
	rep(i, m) {
		V[_u[i]].pb(_v[i]);
		S[_v[i]].pb(_u[i]);
	}
	rep(i, n) deg[i]=V[i].size();
	queue<int>q;
	rep(i, n) if(deg[i]==0) {
		odw[i]=1;
		q.push(i);
	}
	vector<int>P;
	while(true) {
		if(deg[akt]<1 || odw[akt]) return false;
		if(deg[akt]==1) {
			P.pb(akt);
			odw[akt]=1;
			int p=-1;
			for(auto i : V[akt]) if(!odw[i]) p=i;
			if(p==-1) return false;
			for(auto i : S[akt]) {
				--deg[i];
				if(deg[i]<=0 && !odw[i]) {
					odw[i]=1;
					q.push(i);
				}
			}
			akt=p;
			continue;
		}
		if(q.empty()) break;
		int p=q.front(); q.pop();
		for(auto i : S[p]) {
			--deg[i];
			if(deg[i]<=0 && !odw[i]) {
				odw[i]=1;
				q.push(i);
			}
		}
	}
	rep(i, n) V[i].clear();
	rep(i, m) if(!odw[_u[i]] && !odw[_v[i]]) V[_u[i]].pb(_v[i]);
	rep(i, n) odw[i]=0;
	DFS(akt);
	reverse(all(cykl1));
	rep(i, n) odw[i]=0;
	for(auto i : cykl1) czy[i]=1;
	DFS2(V[akt][1]);
	return true;
}

• Subtask 1: 1.75 / 5
• Subtask 2: 1.75 / 5
• Subtask 3: 7.35 / 21
• Subtask 4: 8.399999999999999 / 24
• Subtask 5: 15.749999999999998 / 45