Submission #1062169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062169		AdamGS	Thousands Islands (IOI22_islands)	C++17	100 / 100	315 ms	42580 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<pair<int,int>>G[LIM];
vector<int>V[LIM], S[LIM];
int deg[LIM], odw[LIM], kraw[2*LIM], n, m, akt;
map<pair<int,int>,int>mp;
bool DFS(int x) {
	if(odw[x]) return true;
	odw[x]=1;
	for(auto i : G[x]) {
		if(odw[i.st]) {
			kraw[i.nd]=1;
			return true;
		}
		if(DFS(i.st)) {
			kraw[i.nd]=1;
			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, m) mp[{_u[i], _v[i]}]=i;
	vector<int>K;
	rep(i, (int)P.size()-1) K.pb(mp[{P[i], P[i+1]}]);
	if(P.size()) K.pb(mp[{P.back(), akt}]);
	vector<int>ans;
	for(auto i : K) ans.pb(i);
	rep(i, m) if(!odw[_u[i]] && !odw[_v[i]]) G[_u[i]].pb({_v[i], i});
	rep(i, n) odw[i]=0;
	DFS(akt);
	DFS(G[akt][1].st);
	kraw[G[akt][1].nd]=1;
	rep(i, n) V[i].clear();
	rep(i, m) if(kraw[i]) {
		V[_u[i]].pb(i);
		V[_v[i]].pb(i);
	}
	int p=akt, ile=0, lst=-1;
	while(ile<12) {
		for(auto i : V[p]) if(_u[i]==p && lst!=i) {
			p=_v[i];
			swap(_u[i], _v[i]);
			if(p==akt) ++ile;
			lst=i;
			ans.pb(i);
			break;
		}
	}
	reverse(all(K));
	for(auto i : K) ans.pb(i);
	return ans;
}

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