제출 #1247572

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247572		m5588ohammed	수천개의 섬 (IOI22_islands)	C++20	0 / 100	5 ms	5700 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>,int> fre;
vector <int> cycle,path;
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;
}
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;
		fre[{U[i],V[i]}]++;
	}
	solve(0,-1);
	if(cycle.size()==0) return false;
	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]}]);	
	}
	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