Submission #1042522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042522		Alihan_8	Thousands Islands (IOI22_islands)	C++17	9.10 / 100	103 ms	21232 KiB

islands

#include "islands.h"

#include <variant>
#include <vector>

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define ln '\n';

template <class F, class S>
bool chmin(F &u, const S &v){
	bool flag = false;
	
	if ( u > v ){
		u = v; flag |= true;
	}
	
	return flag;
}

std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
  
	int n = N, m = M;
	
	// subtask #3
	
	vector <vector<int>> adj(n);
	
	map <pair<int,int>,vector<int>> id;
	
	for ( int i = 0; i < m; i++ ){
		adj[U[i]].pb(V[i]);
		
		id[{U[i], V[i]}].pb(i);
	}
	
	vector <int> d(n, n + 1), fa(n, -1);
	
	queue <int> q;
	
	q.push(0); d[0] = 0;
	
	ar <int,2> mt = {-1, -1};
	
	while ( !q.empty() ){
		int u = q.front();
		q.pop();
		
		for ( auto &v: adj[u] ){
			if ( chmin(d[v], d[u] + 1) ){
				q.push(v); fa[v] = u;
			} else if ( d[v] == d[u] + 1 ){
				mt = {u, v};
			}
		}
	}
	
	map <int,int> mp;
	
	int cnt = 0;
	
	for ( auto &x: d ){
		if ( x != n + 1 ){
			mp[x] += 1;
			
			cnt += 1;
		}
	}
	
	if ( (int)mp.size() == cnt && mt[0] == -1 ){
		return false;
	}
	
	if ( mt[0] != -1 ){ // multi_edge
		vector <int> path;
		
		int u = mt[1];
		
		while ( u != -1 ){
			path.pb(u);
			u = fa[u];
		}
		
		reverse(all(path));
		
		int s = path.size();
		
		vector <int> ans;
		
		for ( int i = 0; i + 1 < s; i++ ){
			ans.pb(id[{path[i], path[i + 1]}][0]);
		}
		
		auto tmp = ans;
		
		ans.pb(id[{mt[1], mt[0]}][0]);
		ans.pb(id[{mt[0], mt[1]}][1]);
		ans.pb(id[{mt[1], mt[0]}][1]);
		
		ans.pb(id[{mt[1], mt[0]}][0]);
		ans.pb(id[{mt[0], mt[1]}][1]);
		ans.pb(id[{mt[1], mt[0]}][1]);
		
		for ( int i = s - 2; i >= 0; i-- ){
			ans.pb(tmp[i]);
		}
		
		return ans;
	} else{
		int u = -1, v = -1;
		
		for ( int i = 0; i < n; i++ ){
			for ( int j = i + 1; j < n; j++ ){
				if ( fa[i] == -1 ) continue;
				
				if ( fa[i] == fa[j] ){
					u = i, v = j;
				}
			}
		}
		
		assert(u != -1 && v != -1);
		
		//~ cout << "Debug : " << u << " " << v << ln;
		
		vector <int> path;
		
		int x = fa[u];
		
		while ( x != -1 ){
			path.pb(x);
			x = fa[x];
		}
		
		reverse(all(path));
		
		int s = path.size();
		
		vector <int> ans;
		
		for ( int i = 0; i + 1 < s; i++ ){
			ans.pb(id[{path[i], path[i + 1]}][0]);
		}
		
		auto tmp = ans;
		
		x = fa[u];
		
		ans.pb(id[{x, v}][0]);
		ans.pb(id[{v, x}][0]);
		ans.pb(id[{x, u}][0]);
		ans.pb(id[{u, x}][0]);
		
		ans.pb(id[{x, v}][0]);
		ans.pb(id[{v, x}][0]);
		ans.pb(id[{x, u}][0]);
		ans.pb(id[{u, x}][0]);
		
		for ( int i = s - 2; i >= 0; i-- ){
			ans.pb(tmp[i]);
		}
		
		return ans;
	}
	
	return {};
}

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