Submission #1077921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077921		pcc	Thousands Islands (IOI22_islands)	C++17	1.75 / 100	21 ms	8884 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 a,int b,int now){
	vector<int> rt;
	while(now != 0){
		int eid = up[now];
		rt.push_back(eid);
		now = to[eid^1];
	}
	reverse(rt.begin(),rt.end());

	for(auto it = rt.begin();it != rt.end();it++)ansv.push_back(*it);
	vector<int> tv = {a,a^1,b,b^1,a^1,a,b^1,b};
	for(auto &i:tv)ansv.push_back(i);
	for(auto it = rt.rbegin();it != rt.rend();it++)ansv.push_back(*it);

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

bitset<mxn> vis;

void dfs(int now){
	if(!ansv.empty())return;
	vis[now] = true;
	//cerr<<now<<endl;
	vector<int> cnt;
	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;
		cnt.push_back(eid);
	}
	if(cnt.size()>=2){
		getans(cnt[0],cnt[1],now);
		return;
	}
	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])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;
}

Compilation message (stderr)

islands.cpp: In function 'void dfs(int)':
islands.cpp:57:7: warning: unused variable 'nxt' [-Wunused-variable]
   57 |   int nxt = to[eid];
      |       ^~~

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