Submission #1187772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187772		ByeWorld	Thousands Islands (IOI22_islands)	C++20	22.75 / 100	112 ms	20540 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, ma2;
vector<int> go;

void dfs(int nw, int pa){
	vis[nw] = 1;
	stac.pb(nw);
	for(auto [nx, ed] : adj[nw]){
		if(abs(ed-pa)==1 && u[ed]==v[pa] && u[pa]==v[ed]) 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, ed);
	}
}

void sol(int nw, int pa){
	// cout << nw << " nw\n";
	stac.pb(nw);
	vector<int> vec;
	for(auto [nx, ed] : adj[nw]){
		if(abs(ed-pa)==1 && u[ed]==v[pa] && u[pa]==v[ed]) continue;
		vec.pb(nx);
	}
	if(vec.size() >= 2){
		for(int i=0; i+1<stac.size(); i++) 
			ANS.pb(ma[ pii(stac[i], stac[i+1]) ]);

		int x = vec[0], y = vec[1];
		ANS.pb(ma[pii(nw,x)]);
		ANS.pb(ma[pii(x,nw)]);
		ANS.pb(ma[pii(nw,y)]);
		ANS.pb(ma[pii(y,nw)]);

		ANS.pb(ma[pii(x,nw)]);
		ANS.pb(ma[pii(nw,x)]);
		ANS.pb(ma[pii(y,nw)]);
		ANS.pb(ma[pii(nw,y)]);

		for(int i=stac.size()-1; i>=1; i--) 
			ANS.pb(ma[ pii(stac[i-1], stac[i]) ]);
		return;
	}

	for(auto [nx, ed] : adj[nw]){
		if(ANS.size()) return;
		if(abs(ed-pa)==1 && u[ed]==v[pa] && u[pa]==v[ed]) continue;
		sol(nx, ed);
	}
	stac.pop_back();
}
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});
	}
	for(int i=0; i<m; i++){
		if(ma[pii(u[i], v[i])] == i) continue;
		ma2[pii(u[i], v[i])] = i;
	}
	dfs(1, -1);

	// for(auto in : cyc){
	// 	cout << in << " in\n";
	// }
	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]);

		if(cyc.size() == 3){
			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(ma2[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(ma2[pii(nx, cyc[i])]);
			}
		} else {
			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;
	}
	if(adj[1].size() >= 2){
		int x = adj[1][0].fi, y = adj[1][1].fi;
		ANS.pb(ma[pii(1,x)]);
		ANS.pb(ma[pii(x,1)]);
		ANS.pb(ma[pii(1,y)]);
		ANS.pb(ma[pii(y,1)]);

		ANS.pb(ma[pii(x,1)]);
		ANS.pb(ma[pii(1,x)]);
		ANS.pb(ma[pii(y,1)]);
		ANS.pb(ma[pii(1,y)]);
		return ANS;
	}

	stac.clear();
	sol(1,-1);
	if(ANS.size()) return ANS;

	return false;
}

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