Submission #1062096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062096		jamjanek	Thousands Islands (IOI22_islands)	C++17	9.10 / 100	171 ms	65056 KiB

islands

#include "islands.h"
#include<bits/stdc++.h>
using namespace std;

int stopien_wyjscia[100010];
set<pair<int, int>>graf[100010], graf1[100010];
bool usuniete[100010];
vector<int>answer;

bool czy[100010];
bool odw1[100010];
vector<int>stos;
bool flaga_znaleziono = 0;
void dfs(int start){
	czy[start] = 1;
	odw1[start] = 1;
	for(auto j: graf[start]){
		if(czy[j.first]){
			stos.push_back(j.second);
			flaga_znaleziono = 1;
			return;
		}
		if(!odw1[j.first]){
			stos.push_back(j.second);
			dfs(j.first);
			if(flaga_znaleziono)return;
			stos.pop_back();
		}
	}
	czy[start] = 0;
}



variant<bool, std::vector<int>> find_journey(int n, int m, std::vector<int> U, std::vector<int> V) {
	
	int i;
	for(i=0;i<m;i++){
		graf[U[i]].insert({V[i], i});
		graf1[V[i]].insert({U[i], i});
		stopien_wyjscia[U[i]]++;
		
		//graf[V[i]].push_back({U[i], i+1});
	}
	int start = 0;
	queue<int>kolejka;
	for(i=0;i<n;i++)
		if(stopien_wyjscia[i]==0)
			kolejka.push(i);
	vector<int>poczatek;
	while(true){
//		printf("%d\n", start);
//		for(i=0;i<n;i++)printf("%d ", stopien_wyjscia[i]);printf("\n");
		if(stopien_wyjscia[start]==0)return false;
		if(stopien_wyjscia[start]==1){
			for(auto j: graf1[start])
				if(--stopien_wyjscia[j.first]==0)
					kolejka.push(j.first);
			usuniete[start] = 1;
			for(auto j: graf[start])
				if(!usuniete[j.first]){
					start = j.first;
					answer.push_back(j.second);
					break;
				}
			continue;
		}
		if(!kolejka.size())break;
		
		auto x = kolejka.front();
		kolejka.pop();
		if(usuniete[x])continue;
		usuniete[x] = 1;
		for(auto j: graf1[x])
			if(--stopien_wyjscia[j.first]==0)
				kolejka.push(j.first);
	}
	if(stopien_wyjscia[start]<=1)return false;
	poczatek = answer;

	for(i=0;i<n;i++){
		vector<pair<int,int>>do_usu;
		for(auto j: graf[i])
			if(usuniete[j.first])do_usu.push_back(j);
		for(auto j: do_usu)
			graf[i].erase(j);
	}
	
	czy[start] = 1;
	odw1[start] = 1;
	stos.push_back((*graf[start].begin()).second);
	dfs((*graf[start].begin()).first);
	
	vector<int>pierwsza = stos;
	stos.clear();

	for(i=0;i<n;i++)odw1[i] = 0;
	czy[start] = 1;
	odw1[start] = 1;
	stos.push_back((*graf[start].rbegin()).second);
	if(!czy[(*graf[start].rbegin()).second])
		dfs((*graf[start].rbegin()).second);
	
	vector<int>druga = stos;
//	for(auto j: pierwsza)printf("%d ", j);printf("\n");
//	for(auto j: druga)printf("%d ", j);printf("\n");
	
	for(i=0;i<n;i++)graf[i].clear();
	
	for(auto j: pierwsza)
		graf[U[j]].insert({V[j], j});
	for(auto j: druga)
		graf[U[j]].insert({V[j], j});
	int x = start;
	int policz = 0, pop = -1;
	while(true){
//		printf("%d, ", x);
		if(x==start)policz++;
		if(policz==13)break;
		auto it = *graf[x].begin();
		if(it.second==pop)
			it = *graf[x].rbegin();
		answer.push_back(it.second);
		graf[x].erase(it);
		graf[it.first].insert({x, it.second});
		x = it.first;
		pop = it.second;
	}
	
	while(poczatek.size()){
		answer.push_back(poczatek.back());
		poczatek.pop_back();
	}
	return answer;
}

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