Submission #1077894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077894		pcc	Thousands Islands (IOI22_islands)	C++17	0 / 100	1119 ms	721092 KiB

islands

#include "islands.h"

#include <variant>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 4e5+10;
int head[mxn],nid[mxn],to[mxn];
int ecnt = 0;
int up[mxn];

void add_edge(int a,int b){
	nid[ecnt] = head[a];
	head[a] = ecnt;
	to[ecnt] = b;
	ecnt++;
	return;
}

vector<int> ansv;

void getans(int cyc,int now){
	vector<int> v;
	v.push_back(cyc);
	while(now != to[cyc]){
		int eid = up[now];
		v.push_back(eid);
		now = to[eid^1];
	}
	reverse(v.begin(),v.end());
	vector<int> rt;
	while(now != 0){
		int eid = up[now];
		rt.push_back(eid);
		now = to[eid^1];
	}
	reverse(rt.begin(),rt.end());

	/*
	cerr<<"ANS: "<<endl;
	for(auto &i:rt)cerr<<to[i]<<' ';cerr<<endl;
	for(auto &i:v)cerr<<to[i]<<' ';cerr<<endl;
	*/

	for(auto it = rt.begin();it != rt.end();it++)ansv.push_back(*it);
	for(auto it = v.begin();it != v.end();it++)ansv.push_back(*it);
	for(auto it = v.rbegin();it != v.rend();it++)ansv.push_back((*it)^1);
	for(auto it = v.rbegin();it != v.rend();it++)ansv.push_back(*it);
	for(auto it = v.begin();it != v.end();it++)ansv.push_back((*it)^1);
	for(auto it = rt.rbegin();it != rt.rend();it++)ansv.push_back(*it);
	return;
}

bitset<mxn> vis;

void dfs(int now){
	if(!ansv.empty())return;
	vis[now] = true;
	//cerr<<now<<endl;
	for(int eid = head[now];eid != -1;eid = nid[eid]){
		if(!ansv.empty())return;
		int nxt = to[eid];
		//cerr<<now<<' '<<nxt<<":"<<eid<<endl;
		if((eid^1) == up[now])continue;
		if(vis[nxt]){
			getans(eid,now);
			return;
		}
		else{
			up[nxt] = eid;
			dfs(nxt);
		}
	}
	return;
}

std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
	memset(head,-1,sizeof(head));
	for(int i = 0;i<M;i++){
		int a = U[i],b = V[i];
		add_edge(a,b);
	}
	memset(up,-1,sizeof(up));
	dfs(0);
	if(!ansv.empty())return ansv;
	else return false;
}

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