Submission #1170700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170700		thelegendary08	Thousands Islands (IOI22_islands)	C++17	1.75 / 100	72 ms	13636 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<vi>adj;
vi from;
vector<bool>vis;
vi cyc;
bool ok = 0;
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);
		}
	}
}
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);
	from[0] = -1;
	map<pii, int>ma;
	for(int i = 0; i<m; i+=2){
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
		ma[mp(u[i], v[i])] = i;
		ma[mp(v[i], u[i])] = i + 1;
	}
	dfs(0, -1);
	if(cyc.empty())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