Submission #955783

#	Time	Username	Problem	Language	Result	Execution time	Memory
955783		n1k	Thousands Islands (IOI22_islands)	C++17	19.25 / 100	32 ms	10324 KiB

islands

#include "islands.h"
	
#include <bits/stdc++.h>
	
using namespace std;
	
vector<vector<array<int, 2>>> g, rg;
vector<int> color, par, del, deg;
	
map<int, int> cache;
	
int dfs(int u, int p){
	par[u] = p;
	color[u] = 1;


	for(auto [v, e]:g[u]){
		if(v==p){
			deg[u]--;
		}
	}

	if(deg[u]>1)
		return 1;

	bool ok = 0;

	for(auto [v, e]:g[u]){
		if(del[v] or color[v])
			continue;
		ok |= dfs(v, u);
	}

	return ok;
}
	
std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {
	g.assign(N, {});
	rg.assign(N, {});
	color.assign(N, {});
	par.assign(N, {});
	del.assign(N, {});
	deg.assign(N, {});
	
	for(int i=0; i<M; i++){
		g[U[i]].push_back({V[i], i});
		rg[V[i]].push_back({U[i], i});
	}

	queue<int> q;
	for(int i=0; i<N; i++){
		deg[i]=g[i].size();
		if(deg[i]==0){
			q.push(i);
		}
	}
	while(q.size()){
		auto u = q.front();
		q.pop();
		del[u]=1;
		for(auto [v, e]:rg[u]){
			if(--deg[v]==0){
				q.push(v);
			}
		}
	}

	return dfs(0, 0)==1;

}

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