제출 #1061954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1061954		AdamGS	수천개의 섬 (IOI22_islands)	C++17	35 / 100	76 ms	17940 KiB

islands

#include "islands.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
vector<int>V[LIM], S[LIM];
int deg[LIM], odw[LIM], n, m;
variant<bool,vector<int>>find_journey(int _n, int _m, vector<int>_u, vector<int>_v) {
	n=_n; m=_m;
	rep(i, m) {
		V[_u[i]].pb(_v[i]);
		S[_v[i]].pb(_u[i]);
	}
	rep(i, n) deg[i]=V[i].size();
	queue<int>q;
	rep(i, n) if(deg[i]==0) {
		odw[i]=1;
		q.push(i);
	}
	int akt=0;
	while(true) {
		if(deg[akt]<1 || odw[akt]) return false;
		if(deg[akt]==1) {
			odw[akt]=1;
			int p=-1;
			for(auto i : V[akt]) if(!odw[i]) p=i;
			if(p==-1) return false;
			for(auto i : S[akt]) {
				--deg[i];
				if(deg[i]<=0 && !odw[i]) {
					odw[i]=1;
					q.push(i);
				}
			}
			akt=p;
			continue;
		}
		if(q.empty()) break;
		int p=q.front(); q.pop();
		for(auto i : S[p]) {
			--deg[i];
			if(deg[i]<=0 && !odw[i]) {
				odw[i]=1;
				q.push(i);
			}
		}
	}
	return true;
}

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