Submission #1247585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247585		m5588ohammed	Thousands Islands (IOI22_islands)	C++20	0 / 100	6 ms	5956 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector <int> v[200001];
int vis[200001];
map <array<int,2>,int> mp;
map <array<int,2>,vector <int>> mp2;
map <array<int,2>,int> fre;
vector <int> cycle,path,two;
int solve(int i,int last){
	vis[i]=1;
	for(int j:v[i]){
		if(last!=j&&vis[j]==1){
			cycle.push_back(i);
			return j;
		}
		if(vis[j]==0){
			int val=solve(j,i);
			if(val>=0){
				cycle.push_back(i);
				if(val==i) return -2;
				else return val;
			}
			else if(val==-2){
				path.push_back(i);
				return -2;
			}
		}
	}
	return -1;
}
int solve2(int i,int last){
	for(int j:v[i]){
		if(fre[{i,j}]>=2&&fre[{j,i}]>=1){
			two.push_back(i);
			two.push_back(j);
			return -2;
		}
		if(j!=last&&solve2(j,i)==-2){
			path.push_back(i);
			return -2;
		}
	}
	return -1;
}
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++){
		if(mp.count({U[i],V[i]})==0) v[U[i]].push_back(V[i]);
		mp[{U[i],V[i]}]=i;
		mp2[{U[i],V[i]}].push_back(i);
		fre[{U[i],V[i]}]++;
	}
	solve(0,-1);
	if(cycle.size()!=0){
		reverse(path.begin(),path.end());
		reverse(cycle.begin(),cycle.end());
		vector <int> ans;
		for(int i=0;i<path.size()-1;i++){
			ans.push_back(mp[{path[i],path[i+1]}]);
		}
		ans.push_back(mp[{path.back(),cycle[0]}]);
		ans.push_back(mp[{cycle[0],cycle.back()}]);
		ans.push_back(mp[{cycle.back(),cycle[0]}]);
		for(int i=0;i<cycle.size()-1;i++){
			ans.push_back(mp[{cycle[i],cycle[i+1]}]);	
		}
		ans.push_back(mp[{cycle[0],cycle.back()}]);
		ans.push_back(mp[{cycle.back(),cycle[0]}]);
		for(int i=cycle.size()-1;i>=1;i--){
			ans.push_back(mp[{cycle[i-1],cycle[i]}]);	
		}
		ans.push_back(mp[{path.back(),cycle[0]}]);
		for(int i=path.size()-1;i>0;i--){
			ans.push_back(mp[{path[i-1],path[i]}]);
		}
		return ans;
	}
	else{
		path.clear();
		solve2(0,-1);
		if(two.size()==0) return false;
		reverse(path.begin(),path.end());
		vector <int> ans;
		for(int i=0;i<path.size()-1;i++){
			ans.push_back(mp[{path[i],path[i+1]}]);
		}
		ans.push_back(mp[{path.back(),two[0]}]);
		ans.push_back(mp2[{two[0],two[1]}][0]);
		ans.push_back(mp2[{two[1],two[0]}][0]);
		ans.push_back(mp2[{two[0],two[1]}][1]);
		ans.push_back(mp2[{two[0],two[1]}][0]);
		ans.push_back(mp2[{two[1],two[0]}][0]);
		ans.push_back(mp2[{two[0],two[1]}][1]);
		ans.push_back(mp[{path.back(),two[0]}]);
		for(int i=path.size()-1;i>0;i--){
			ans.push_back(mp[{path[i-1],path[i]}]);
		}
		return ans;
	}
}
// 6 12
// 0 3
// 3 0
// 3 2
// 2 3
// 1 2
// 2 1
// 1 4
// 4 1
// 5 4
// 4 5
// 2 5
// 5 2

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