Submission #1170713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170713		thelegendary08	Thousands Islands (IOI22_islands)	C++17	1.75 / 100	426 ms	37912 KiB

islands

#include "islands.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define f0r(i,n) for(int i = 0;  i< n; i++)
#define mp make_pair
#define pii pair<int,int>
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<'\n';
using namespace std;
vector<set<int>>adj;
vi from;
vector<bool>vis;
vi cyc;
bool ok = 0;
vector<int>doob;
void dfs(int x, int fr){
	if(ok)return;
	vis[x] = 1;
	for(auto u : adj[x]){
		if(u == fr)continue;
		if(ok)return;
		if(vis[u]){
			cyc.pb(u); cyc.pb(x);
			ok = 1;
			return;
		}
		else{
			from[u] = x;
			dfs(u, x);
		}
	}
}
void dfs2(int x){
	if(ok)return;
	vis[x] = 1;
	if(doob[x] != -1){
		cyc.pb(x);
		cyc.pb(doob[x]);
		ok = 1;
		return;
	}
	for(auto u : adj[x]){
		if(vis[u])continue;
		if(ok)return;
		
		from[u] = x;
		dfs2(u);
		
	}
}
std::variant<bool, std::vector<int>> find_journey(
    int n, int m, std::vector<int> u, std::vector<int> v) {
	adj.resize(n);
	from.resize(n);
	vis.resize(n);
	doob.resize(n);
	f0r(i, n)doob[i] = -1;
	from[0] = -1;
	map<pii, int>ma;
	map<pii, vector<int>>dub;
	for(int i = 0; i<m; i+=2){
		adj[u[i]].insert(v[i]);
		adj[v[i]].insert(u[i]);
		ma[mp(u[i], v[i])] = i;
		ma[mp(v[i], u[i])] = i + 1;
		dub[mp(u[i], v[i])].pb(i);
		dub[mp(v[i], u[i])].pb(i+1);
	}
	for(auto u : dub){
		if(u.second.size() > 1){
			doob[u.first.first] = u.first.second;
			doob[u.first.second] = u.first.first;
		}
	}
	dfs(0, -1);
	if(cyc.empty()){
		f0r(i,n)vis[i] = 0;
		f0r(i, n)from[i] = 0;
		from[0] = -1;
		ok = 0;
		dfs2(0);
		if(!cyc.empty()){
			// cout<<"HI"<<'\n';
			vi c2;
			c2.pb(cyc[0]);
			while(c2.back() != 0){
				c2.pb(from[c2.back()]);
			}
			reverse(c2.begin(), c2.end());
			// vout(c2);
			vi ans;
			f0r(i, c2.size() - 1){
				ans.pb(ma[mp(c2[i], c2[i+1])]);
			}
			// vout(ans);
			int a1 = dub[mp(cyc[0], cyc[1])][0];
			int b1 = dub[mp(cyc[0], cyc[1])][1];
			int c1 = dub[mp(cyc[1], cyc[0])][0];
			ans.pb(a1);
			ans.pb(c1);
			ans.pb(b1);
			ans.pb(a1);
			ans.pb(c1);
			ans.pb(b1);
			// vout(ans);
			for(int i = c2.size() - 2; i>=0; i--){
				ans.pb(ma[mp(c2[i+1], c2[i])]);
			}
			
			return ans;
		}
		else return false;
	}
	else{
		// vout(cyc);
		while(cyc.back() != 0){
			cyc.pb(from[cyc.back()]);
		}
		int st = 0;
		
		reverse(cyc.begin(), cyc.end());
		f0r(i, cyc.size()){
			if(cyc[i] == cyc.back()){
				st = i;
				break;
			}
		}
		// vout(from);
		// vout(cyc);
		// cout<<st<<'\n';
		vi ans;
		f0r(i, st){
			ans.pb(ma[mp(cyc[i], cyc[i+1])]);
		}
		// vout(ans);
		FOR(i, st, cyc.size() - 1){
			ans.pb(ma[mp(cyc[i], cyc[i+1])]);
		}
		// vout(ans);
		for(int i = cyc.size() - 1; i>st; i--){
			ans.pb(ma[mp(cyc[i], cyc[i-1])]);
		}
		// vout(ans);
		for(int i = cyc.size() - 1; i>st; i--){
			ans.pb(ma[mp(cyc[i-1], cyc[i])]);
		}
		// vout(ans);
		FOR(i, st, cyc.size() - 1){
			ans.pb(ma[mp(cyc[i+1], cyc[i])]);
		}
		// vout(ans);
		for(int i = st - 1; i>=0; i--){
			ans.pb(ma[mp(cyc[i+1], cyc[i])]);
		}
		// vout(ans);
		return ans;
	}
	
}

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