Submission #1010309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010309		CSQ31	Thousands Islands (IOI22_islands)	C++17	38.25 / 100	90 ms	47648 KiB

islands

#include "islands.h"
#include<bits/stdc++.h>
#include <variant>
#include <vector>
using namespace std;
#define sz(a) (int)(a.size())
#define pb push_back
#define fi first
#define se second
typedef pair<int,int> pii;
const int MAXN = 5e5+5;
bool dead[MAXN],mark[MAXN];
int outdeg[MAXN],par[MAXN],vis[MAXN];
vector<pii>g[MAXN],gr[MAXN];
vector<int>path,cycle;

void rev(vector<int>&a){reverse(a.begin(),a.end());}
bool dfs(int v,int root){
	vis[v] = 1;
	for(pii z:g[v]){
		int x = z.fi;
		if(mark[x])continue;
		if(vis[x]){
			int cur = v;
			while(cur != x){
				cycle.pb(cur);
				cur = par[cur];
			}
			cycle.pb(x);
			rev(cycle);
			if(cur != root){
				while(cur != root){
					path.pb(cur);
					cur = par[cur];
				}
			}
			path.pb(root);
			rev(path);
			return 1;
		}else{
			par[x] = v;
			if(dfs(x,root))return 1;
		}
	}
	return 0;
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V){
	for(int i=0;i<M;i++){
		gr[V[i]].pb({U[i],i});
		g[U[i]].pb({V[i],i});
		outdeg[U[i]]++;
	}
	vector<int>del;
	for(int i=0;i<N;i++){
		//cout<<i<<" "<<sz(g[i])<<'\n';
		if(g[i].empty()){
			del.pb(i);
			mark[i] = 1;
		}
	}
	int cur = 0;
	vector<int>ans;
	while(true){
		if(mark[cur])return false;
		while(!del.empty()){
			vector<int>tmp;
			for(int u:del){
				//cout<<u<<'\n';
				for(pii x:gr[u]){
					int v = x.fi;
					outdeg[v]--;
					dead[x.se] = 1;
					if(!outdeg[v] && !mark[v]){
						tmp.pb(v);
						mark[v] = 1;
					}
				}
			}
			del = tmp;
		}
		if(mark[cur])return false;
		int cnt = 0;
		for(pii x:g[cur]){
			if(!mark[x.fi])cnt++;
		}
		if(cnt > 1)break;
		if(cnt == 0)return false;
		for(pii x:g[cur]){
			if(!mark[x.fi]){
				del.pb(cur);
				mark[cur] = 1;
				ans.pb(x.se);
				cur = x.fi;
				break;
			}
		}

	}
	int fix = 0;
	vector<vector<int>>p,c;
	for(pii x:g[cur]){
		if(mark[x.fi])continue;
		if(sz(p)>1)break;
		path.clear();
		cycle.clear();
		for(int i=0;i<N;i++)vis[i] = par[i] = 0;
		fix = x.se;
		vis[cur] = 1;
		par[x.fi] = cur;
		dfs(x.fi,cur);

		p.pb(path);
		c.pb(cycle);
	}
	bool case2 = 0;
	vector<int>tmp = ans;
	vector<int>p1,p2,c1,c2;
	vector<bool>incyc(N,0);
	for(int i=0;i+1<sz(p[0]);i++){
		int v = p[0][i];
		int u = p[0][i+1];
		for(pii x:g[v]){
			if(x.fi == u){
				p1.pb(x.se);
				break;
			}
		}
	}
	for(int i=0;i<sz(c[0]);i++){
		int v = c[0][i];
		int u = c[0][(i+1)%sz(c[0])];
		incyc[v] = 1;

		for(pii x:g[v]){
			if(x.fi == u){
				c1.pb(x.se);
				break;
			}
		}
	}
	
	int tail = 0;
	for(int i=0;i+1<sz(p[1]);i++){
		int v = p[1][i];
		int u = p[1][i+1];
		for(pii x:g[v]){
			if(x.fi == u){
				if(i)p2.pb(x.se);
				else p2.pb(fix);
				break;
			}
		}
		if(incyc[u]){
			tail = u;
			case2 = 1;
			break;
		}
	}
	if(!case2){
		for(int i=0;i<sz(c[1]);i++){
			int v = c[1][i];
			int u = c[1][(i+1)%sz(c[1])];
			for(pii x:g[v]){
				if(x.fi == u){
					c2.pb(x.se);
					break;
				}
			}
			if(incyc[u]){
				tail = u;
				case2 = 1;
				break;
			}
		}
	}
	//////
	if(case2){
		for(int x:p1)ans.pb(x);
		for(int x:c1)ans.pb(x);
		rev(p1);
		for(int x:p1)ans.pb(x);

		for(int x:c2)p2.pb(x);
		for(int x:p2)ans.pb(x);

		int shft = 0;
		for(int i=0;i<sz(c[0]);i++){
			if(c[0][(i+1)%sz(c[0])]==tail){
				shft = i;
				break;
			}
		}
		int m = sz(c1);
		for(int i=0;i<sz(c1);i++)ans.pb(c1[(shft+m-i)%m]);
		rev(p2);
		for(int x:p2)ans.pb(x);
	}else{
		for(int x:p1)ans.pb(x);
		for(int x:c1)ans.pb(x);
		rev(p1);
		for(int x:p1)ans.pb(x);
		rev(p1);rev(c1);

		for(int x:p2)ans.pb(x);
		for(int x:c2)ans.pb(x);
		rev(p2);
		for(int x:p2)ans.pb(x);
		rev(p2);rev(c2);

		for(int x:p1)ans.pb(x);
		for(int x:c1)ans.pb(x);
		rev(p1);
		for(int x:p1)ans.pb(x);
		rev(p1);

		for(int x:p2)ans.pb(x);
		for(int x:c2)ans.pb(x);
		rev(p2);
		for(int x:p2)ans.pb(x);
		rev(p2);

	}
	rev(tmp);
	for(int x:tmp)ans.pb(x);
	return ans;

}

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