Submission #881571

#	Time	Username	Problem	Language	Result	Execution time	Memory
881571		djs100201	Thousands Islands (IOI22_islands)	C++17	19.25 / 100	75 ms	38680 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_];
set<P>edge[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{
			for(int i=1;i<=n;i++){
				if(i==now || !v[i].size())continue;
				a=*v[i].begin();
				//v[i].clear();
				edge[i].insert({-1,a});
				//v[i].insert(a);
			}
			a=*v[now].begin();
			auto it=v[now].end();
			it--;
			b=*it;
			edge[now].insert({-1,a});
			ret.push_back(now);
			x=now;
			while(1){
				ret.push_back(x);
				if(x==now)break;
				P nxt=*edge[x].begin();
				edge[nxt.second].insert({1,x});
				x=nxt.first;
			}
			edge[now].clear();
			edge[now].insert({-1,b});
			ret.push_back(now);
			x=now;
			while(1){
				ret.push_back(x);
				if(x==now)break;
				P nxt=*edge[x].begin();
				edge[nxt.second].insert({1,x});
				x=nxt.first;
			}

			edge[now].clear();
			edge[now].insert({-1,a});
			ret.push_back(now);
			x=now;
			while(1){
				ret.push_back(x);
				if(x==now)break;
				P nxt=*edge[x].begin();
				edge[nxt.second].insert({1,x});
				x=nxt.first;
			}
			edge[now].clear();
			edge[now].insert({-1,b});
			ret.push_back(now);
			x=now;
			while(1){
				ret.push_back(x);
				if(x==now)break;
				P nxt=*edge[x].begin();
				edge[nxt.second].insert({1,x});
				x=nxt.first;
			}
			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