Submission #1187750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187750		ByeWorld	Thousands Islands (IOI22_islands)	C++20	0 / 100	55 ms	17596 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
#include <variant>
#include <vector>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf ((id<<1))
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 2e5+10;
typedef pair<int,int> pii;

int n, m;
int u[MAXN], v[MAXN];
vector<int> ANS;
vector<pii> adj[MAXN];
bool vis[MAXN];
vector<int> stac, cyc;
map<pii,int> ma;
vector<int> go;

void dfs(int nw, int pa){
	vis[nw] = 1;
	stac.pb(nw);
	for(auto [nx, ed] : adj[nw]){
		if(nx == pa) continue;
		if(!cyc.empty()) return;

		if(vis[nx]){
			while(stac.back() != nx){
				cyc.pb(stac.back()); stac.pop_back();
			}
			cyc.pb(nx);

			int ba = stac.back(); stac.pop_back();
			while(!stac.empty()){
				go.pb(ma[pii(stac.back(), ba)]);
				ba = stac.back(); stac.pop_back();
			}
			return;
 		} else dfs(nx, nw);
	}
}

std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
	n = N; m = M;
	for(int i=0; i<m; i++){
		u[i] = U[i]+1, v[i] = V[i]+1;
		ma[pii(u[i], v[i])] = i; 
		adj[u[i]].pb({v[i], i});
		adj[v[i]].pb({u[i], i});
	}
	dfs(1, 0);

	if(!cyc.empty()){
		reverse(cyc.begin(), cyc.end());
		for(int i=go.size()-1; i>=0; i--) ANS.pb(go[i]);
		cyc.pb(cyc[0]);

		for(int i=0; i+1<cyc.size(); i++){ // ac
			int nx = cyc[i+1];
			ANS.pb(ma[pii(cyc[i], nx)]);
		}
		for(int i=cyc.size()-1; i>=1; i--){ // fd
			int nx = cyc[i-1];
			ANS.pb(ma[pii(cyc[i], nx)]);
		}
		for(int i=cyc.size()-1; i>=1; i--){ // fd
			int nx = cyc[i-1];
			ANS.pb(ma[pii(nx, cyc[i])]);
		}
		for(int i=0; i+1<cyc.size(); i++){ // ac
			int nx = cyc[i+1];
			ANS.pb(ma[pii(nx, cyc[i])]);
		}
		for(int i=0; i<go.size(); i++) ANS.pb(go[i]);
		return ANS;
	}
	return false;
}

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