Submission #1170836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170836		thelegendary08	Thousands Islands (IOI22_islands)	C++17	22.75 / 100	305 ms	37916 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;
pii branch;
int st;
bool ok = 0;
vector<int>doob;
void dfs(int x, int fr){
	if(ok)return;
	vis[x] = 1;
	int cnt = adj[x].size();
	if(fr != -1)cnt--;
	if(cnt >= 2){
		st = x;
		vi brr;
		for(auto u : adj[x]){
			if(u == fr)continue;
			brr.pb(u);
			if(brr.size() == 2)break;
		}
		branch = mp(brr[0], brr[1]);
		ok = 1;
		return;
	}
	for(auto u : adj[x]){
		if(u == fr)continue;
		if(ok)return;
		else{
			from[u] = x;
			dfs(u, x);
		}
	}
}
void dfs2(int x){
	if(ok)return;
	vis[x] = 1;
	if(doob[x] != -1){
		st = 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(ok){
		vi chain;
		chain.pb(st);
		while(chain.back() != 0)chain.pb(from[chain.back()]);
		reverse(chain.begin(), chain.end());
		vi nums;
		f0r(i, chain.size() - 1){
			nums.pb(ma[mp(chain[i], chain[i + 1])]);
		}
		int a = ma[mp(st, branch.first)];
		int b = ma[mp(branch.first, st)];
		int c = ma[mp(st, branch.second)];
		int d = ma[mp(branch.second, st)];
		
		vi ans;
		for(auto u : nums){
			ans.pb(u);
		}
		ans.pb(a);
		ans.pb(b);
		ans.pb(c);
		ans.pb(d);
		ans.pb(b);
		ans.pb(a);
		ans.pb(d);
		ans.pb(c);
		for(int i = nums.size() - 1; i>=0; i--)ans.pb(nums[i]);
		// cout<<st<<' '<<branch.first<<' '<<branch.second<<'\n';
		return ans;
	}
	else{
		f0r(i,n){
			from[i] = 0;
			vis[i] = 0;
		}
		from[0] = -1;
		dfs2(0);
		if(ok){
			vi ans;
			vi chain;
			chain.pb(st);
			while(chain.back() != 0)chain.pb(from[chain.back()]);
			reverse(chain.begin(), chain.end());
			vi nums;
			f0r(i, chain.size() - 1){
				nums.pb(ma[mp(chain[i], chain[i + 1])]);
			}
			for(auto u : nums){
				ans.pb(u);
			}
			int a1 = dub[mp(st, doob[st])][0];
			int b1 = dub[mp(st, doob[st])][1];
			int c1 = dub[mp(doob[st], st)][0];
			ans.pb(a1);
			ans.pb(c1);
			ans.pb(b1);
			ans.pb(a1);
			ans.pb(c1);
			ans.pb(b1);
			for(int i = nums.size() - 1; i>=0; i--)ans.pb(nums[i]);
			return ans;
		}
		else return false;
		
	}
	
}

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