Submission #630639

#	Time	Username	Problem	Language	Result	Execution time	Memory
630639		errorgorn	Thousands Islands (IOI22_islands)	C++17	100 / 100	134 ms	30472 KiB

islands

#include "islands.h"
 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
 
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
 
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
 
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
 
int n,m;
vector<ii> al[200005];
ii edges[200005];
bool down[200005];
 
bool vis[200005];
bool onstk[200005];
int in[200005];
ii mx[200005];
int pp[200005];
int CTIME=1;
 
void dfs(int i){
	vis[i]=true;
	onstk[i]=true;
	in[i]=CTIME++;
	mx[i]=ii(-1,-1);
 
	for (auto [it,id]:al[i]){
		if (!vis[it]){
			pp[it]=id;
			dfs(it);
			down[id]=true;
		}
 
		if (onstk[it]){
			mx[i]=max(mx[i],{in[it],id});
		}
		else{
			mx[i]=max(mx[i],mx[it]);
			down[id]=true;
		}
	}
 
	onstk[i]=false;
}
;
bool get(int i,vector<int> &v){
	vis[i]=true;
	onstk[i]=true;
 
	for (auto [it,id]:al[i]){
		if (!vis[it]){
			if (get(it,v)){
				v.pub(id);
				return true;
			}
		}
		if (onstk[it]){
			v.pub(id);
			return true;
		}
	}
 
	onstk[i]=false;
	return false;
}
 
variant<bool, vector<signed>> find_journey(
  signed N, signed M, vector<signed> U, vector<signed> V) {
 
	n=N,m=M;
 
	rep(x,0,m){
		al[U[x]].pub({V[x],x});
		edges[x]={U[x],V[x]};
	}
 
	dfs(0);
 
	//rep(x,0,n) cout<<in[x]<<" "; cout<<endl;
	//rep(x,0,n) cout<<mx[x]<<" "; cout<<endl;
 
	//rep(x,0,n) cout<<pp[x]<<" "; cout<<endl;
 
	rep(x,0,n) if (vis[x]){
		vector<ii> v;
		for (auto [it,id]:al[x]) if (down[id] && mx[it].fi>=in[x]) v.pub({it,id});
 
		if (sz(v)>=2){
			vector<int> head;
			int curr=x;
			while (curr){
				head.pub(pp[curr]);
				curr=edges[pp[curr]].fi;
			}
 
			vector<signed> ans;
			rep(x,sz(head),0) ans.pub(head[x]);
 
			while (sz(v)>2) v.pob();
 
			vector<int> tail[2],cyc[2];
			rep(y,0,2){
				memset(vis,false,sizeof(vis));
				memset(onstk,false,sizeof(onstk));
				onstk[x]=true;
				for (auto it:head) vis[edges[it].fi]=true;
				vis[x]=true;
 
				vector<int> idx;
				get(v[y].fi,idx);
				idx.pub(v[y].se);
 
				reverse(all(idx));
 
 
				vector<int> idx1,idx2;
				bool f=true;
				for (auto it:idx){
					if (edges[it].fi==edges[idx.back()].se) f=false;
					if (f) tail[y].pub(it);
					else cyc[y].pub(it);
				}
 
				//cout<<"debug: "<<v[y].fi<<endl;
				//for (auto it:tail[y]) cout<<it<<" "; cout<<endl;
				//for (auto it:cyc[y]) cout<<it<<" "; cout<<endl;
			}
 
			set<int> s;
			rep(x,0,2) for (auto it:cyc[x]) s.insert(it);
 
			if (sz(s)==sz(cyc[0])+sz(cyc[1])){
				rep(x,0,4){
					rep(y,0,sz(tail[x%2])) ans.pub(tail[x%2][y]);
					if (x/2==0){
						rep(y,0,sz(cyc[x%2])) ans.pub(cyc[x%2][y]);
					}
					else{
						rep(y,sz(cyc[x%2]),0) ans.pub(cyc[x%2][y]);
					}
					rep(y,sz(tail[x%2]),0) ans.pub(tail[x%2][y]);
				}
			}
			else{
				s.clear();
				for (auto it:cyc[0]) s.insert(it);
 
				vector<int> tail2[2];
 
				rep(x,0,2){
					vector<int> temp;
					for (auto it:tail[x]) temp.pub(it);
					for (auto it:cyc[x]) temp.pub(it);
					for (auto it:temp){
						tail2[x].pub(it);
						if (s.count(it)) break;
					}
				}
 
				//cout<<"testing: "<<endl;
				//for (auto it:tail2[0]) cout<<it<<" "; cout<<endl;
				//for (auto it:tail2[1]) cout<<it<<" "; cout<<endl;
				//for (auto it:cyc[0]) cout<<it<<" "; cout<<endl;
 
				rep(x,0,sz(tail2[0])-1) ans.pub(tail2[0][x]);
				rep(i,0,sz(cyc[0])) if (cyc[0][i]==tail2[0].back()){
					rep(x,i,sz(cyc[0])) ans.pub(cyc[0][x]);
					rep(x,0,i) ans.pub(cyc[0][x]);
				}
				rep(x,sz(tail2[0])-1,0) ans.pub(tail2[0][x]);
 
				rep(x,0,sz(tail2[1])-1) ans.pub(tail2[1][x]);
				rep(i,0,sz(cyc[0])) if (cyc[0][i]==tail2[1].back()){
					rep(x,i,0) ans.pub(cyc[0][x]);
					rep(x,sz(cyc[0]),i) ans.pub(cyc[0][x]);
				}
				rep(x,sz(tail2[1])-1,0) ans.pub(tail2[1][x]);
			}
 
			rep(x,0,sz(head)) ans.pub(head[x]);
 
			return ans;
		}
	}
 
	return false;
}
 

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 24 / 24
• Subtask 5: 45 / 45