Submission #1170847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170847		thelegendary08	Thousands Islands (IOI22_islands)	C++17	0 / 100	1116 ms	1051324 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;
int en;
bool ok = 0;
vector<int>doob;
void dfs(int x, int fr){
	if(ok)return;
	vis[x] = 1;
	for(auto u : adj[x]){
		if(u == fr)continue;
		if(ok)return;
		else if(vis[u]){
			ok = 1;
			st = u;
			en = x;
			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]);
		ma[mp(u[i], v[i])] = i;
	}
	
	for(auto u : ma){
		if(ma.count(mp(u.first.second, u.first.first))){
			doob[u.first.first] = u.first.second;
			doob[u.first.second] = u.first.first;
			dub[mp(u.first.first, u.first.second)].pb(ma[mp(u.first.first, u.first.second)]);
			dub[mp(u.first.first, u.first.second)].pb(ma[mp(u.first.first, u.first.second)] + 1);
			dub[mp(u.first.second, u.first.first)].pb(ma[mp(u.first.second, u.first.first)]);
			dub[mp(u.first.second, u.first.first)].pb(ma[mp(u.first.second, u.first.first)] + 1);
		}
	}
	
	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 sike;
		sike.pb(en);
		while(sike.back() != st)sike.pb(from[sike.back()]);
		reverse(sike.begin(), sike.end());
		sike.pb(sike[0]);
		vi nums;
		f0r(i, chain.size() - 1){
			nums.pb(ma[mp(chain[i], chain[i + 1])]);
		}
		// vout(chain);
		// vout(sike);
		vi ans;
		for(auto u : nums){
			ans.pb(u);
		}
		f0r(i, sike.size() - 1){
			ans.pb(ma[mp(sike[i], sike[i+1])]);
		}
		f0r(i, sike.size() - 1){
			ans.pb(ma[mp(sike[i], sike[i+1])] + 1);
		}
		for(int i = sike.size() - 2; i>=0; i--){
			ans.pb(ma[mp(sike[i], sike[i+1])]);
		}
		for(int i = sike.size() - 2; i>=0; i--){
			ans.pb(ma[mp(sike[i], sike[i+1])] + 1);
		}
		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: 0 / 5
• Subtask 3: 0 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 45