Submission #1062026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062026		jamjanek	Thousands Islands (IOI22_islands)	C++17	11.90 / 100	41 ms	14640 KiB

islands

#include "islands.h"

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

int stopien_wyjscia[100010];
vector<pair<int, int>>graf[100010], graf1[100010];
bool usuniete[100010];
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]].push_back({V[i], i});
		graf1[V[i]].push_back({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);
	while(true){
		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;
					break;
				}
			continue;
		}
		if(!kolejka.size())break;
		auto x = kolejka.front();
		kolejka.pop();
		usuniete[x] = 1;
		for(auto j: graf1[x])
			if(--stopien_wyjscia[j.first]==0)
				kolejka.push(j.first);
	}
	return stopien_wyjscia[start]>=2;
	
}

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