Submission #881564

#	Time	Username	Problem	Language	Result	Execution time	Memory
881564		djs100201	Thousands Islands (IOI22_islands)	C++17	19.25 / 100	76 ms	30496 KiB

islands

#include "islands.h"
#include <variant>
#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 2e5 + 505, inf = (ll)2e9 * (ll)1e9 + 7, mod = 998244353;
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans, k;
vector<ll>rev[n_];
ll prob[n_],out[n_];
set<ll>v[n_];
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++){
		out[U[i]]++;
		v[U[i]].insert(V[i]);
		rev[V[i]].push_back(U[i]);
	}
	fill(prob,prob+n+1,1);
	//가능성이 존재한다.
	queue<ll>q;
	for(int i=1;i<=n;i++){
		if(out[i])continue;
		q.push(i);
	}
	while(q.size()){
		a=q.front();
		q.pop();
		prob[a]=0;
		for(auto nxt:rev[a]){
			out[nxt]--;
			v[nxt].erase(a);
			if(out[nxt]==0){
				q.push(nxt);
			}
		}
	}
	ll now=0;
	vector<int>ret,ret_rev;
	while(1){
		if(!out[now])return false;
		if(out[now]==1){
			ret.push_back(now);
			ret_rev.push_back(now);
			queue<ll>q;
			for(auto nxt:rev[now]){
				out[nxt]--;
				v[nxt].erase(now);
				if(out[nxt]==0)q.push(nxt);
			}
			out[now]=0;
			now=*v[now].begin();
		}
		else{


			return true;
			break;
		}
	}
	reverse(all(ret_rev));
	for(auto i:ret_rev)ret.push_back(i);
    return ret;
}

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