Submission #881850

#	Time	Username	Problem	Language	Result	Execution time	Memory
881850		djs100201	Thousands Islands (IOI22_islands)	C++17	11.90 / 100	1095 ms	51644 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<P>rev[n_];
ll prob[n_],out[n_],checked[n_];
set<P>v[n_],edge[n_];
P To[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],i});
		rev[V[i]].push_back({U[i],i});
	}
	fill(prob,prob+n+1,1);
	//가능성이 존재한다.
	queue<ll>q;
	for(int i=0;i<n;i++){
		if(v[i].size())continue;
		q.push(i);
	}
	while(q.size()){
		a=q.front();
		q.pop();
		prob[a]=0;
		for(auto nxt:rev[a]){
			v[nxt.first].erase({a,nxt.second});
			if(v[nxt.first].size()==0){
				q.push(nxt.first);
			}
		}
	}
	ll now=0;
	vector<int>ret,ret_rev;
	while(1){
		//cout<<now<<' '<<v[now].size()<<endl;
		if(!v[now].size())return false;
		if(v[now].size()==1){
			ret.push_back((*v[now].begin()).second);
			ret_rev.push_back((*v[now].begin()).second);
			queue<ll>q;
			for(auto nxt:rev[now]){
				v[nxt.first].erase({now,nxt.second});
				if(v[nxt.first].size()==0)q.push(nxt.first);
			}
			while(q.size()){
				x=q.front();
				q.pop();
				for(auto nxt:rev[x]){
					v[nxt.first].erase({now,nxt.second});
					if(v[nxt.first].size()==0)q.push(nxt.first);
				}
			}
			out[now]=0;
			now=(*v[now].begin()).first;
		}
		else{
			
			for(int i=0;i<n;i++){
				if(i==now || !v[i].size())continue;
				auto cur=*v[i].begin();
				//v[i].clear();
				edge[i].insert(cur);
				//cout<<i<<' '<<cur.first<<' '<<cur.second<<endl;
				//v[i].insert(a);
			}
			auto a=*v[now].begin();
			//cout<<a<<' '<<b<<endl;
			x=now;
			edge[now].clear();
			edge[now].insert(a);
			for(int i=0;i<n;i++)To[i]={-1,-1};
			while(1){
				P nxt;
				//cout<<x<<endl;
				if(edge[x].size()==1){
					nxt=*edge[x].begin();
				}
				else{
					for(auto i:edge[x]){
						if(i!=To[x])nxt=i;
					}
				}
				To[nxt.first]={x,nxt.second};
				//cout<<x<<' '<<nxt.first<<' '<<nxt.second<<endl;
				edge[nxt.first].insert({x,nxt.second});
				edge[x].erase(nxt);
				ret.push_back(nxt.second);
				x=nxt.first;
				if(x==now)break;
			}
			edge[now].clear();
			auto it=v[now].end();
			it--;
			//cout<<a<<' '<<b<<endl;
			x=now;
			edge[now].insert(*it);
			for(int i=0;i<n;i++)To[i]={-1,-1};
			base=0;
			while(1){
				P nxt;
				//cout<<x<<endl;
				if(edge[x].size()==1){
					nxt=*edge[x].begin();
				}
				else{
					for(auto i:edge[x]){
						if(i!=To[x])nxt=i;
					}
				}
				To[nxt.first]={x,nxt.second};
				//cout<<x<<' '<<nxt.first<<' '<<nxt.second<<endl;
				edge[nxt.first].insert({x,nxt.second});
				edge[x].erase(nxt);
				ret.push_back(nxt.second);
				x=nxt.first;
				if(x==now)break;
			}
			a=*v[now].begin();
			//cout<<a<<' '<<b<<endl;
			x=now;
			edge[now].clear();
			edge[now].insert(a);
			for(int i=0;i<n;i++)To[i]={-1,-1};
			while(1){
				P nxt;
				//cout<<x<<endl;
				if(edge[x].size()==1){
					nxt=*edge[x].begin();
				}
				else{
					for(auto i:edge[x]){
						if(i!=To[x])nxt=i;
					}
				}
				To[nxt.first]={x,nxt.second};
				//cout<<x<<' '<<nxt.first<<' '<<nxt.second<<endl;
				edge[nxt.first].insert({x,nxt.second});
				edge[x].erase(nxt);
				ret.push_back(nxt.second);
				x=nxt.first;
				if(x==now)break;
			}
			edge[now].clear();
			it=v[now].end();
			it--;
			//cout<<a<<' '<<b<<endl;
			x=now;
			edge[now].insert(*it);
			for(int i=0;i<n;i++)To[i]={-1,-1};
			base=0;
			while(1){
				P nxt;
				//cout<<x<<endl;
				if(edge[x].size()==1){
					nxt=*edge[x].begin();
				}
				else{
					for(auto i:edge[x]){
						if(i!=To[x])nxt=i;
					}
				}
				To[nxt.first]={x,nxt.second};
				//cout<<x<<' '<<nxt.first<<' '<<nxt.second<<endl;
				edge[nxt.first].insert({x,nxt.second});
				edge[x].erase(nxt);
				ret.push_back(nxt.second);
				x=nxt.first;
				if(x==now)break;
			}
			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: 0 / 21
• Subtask 4: 8.399999999999999 / 24
• Subtask 5: 0 / 45