Submission #1077957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077957		pcc	Thousands Islands (IOI22_islands)	C++17	24 / 100	27 ms	12632 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];
int par[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){
	cerr<<"ANSWERING";
	vector<int> v;
	v.push_back(cyc);
	while(now != to[cyc]){
		int eid = up[now];
		v.push_back(eid);
		now = par[now];
	}
	reverse(v.begin(),v.end());
	vector<int> rt;
	while(now != 0){
		int eid = up[now];
		rt.push_back(eid);
		now = par[now];
	}
	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.begin();it != v.end();it++)ansv.push_back((*it)^1);
	for(auto it = v.rbegin();it != v.rend();it++)ansv.push_back(*it);
	for(auto it = v.rbegin();it != v.rend();it++)ansv.push_back((*it)^1);
	for(auto it = rt.rbegin();it != rt.rend();it++)ansv.push_back(*it);
	return;
}

int idx[mxn];
int cnt = 0;
vector<int> chain;
bitset<mxn> in;

void dfs(int now,int fa){
	if(!ansv.empty())return;
	chain.push_back(now);
	in[now] = true;
	idx[now] = ++cnt;
	//cerr<<now<<endl;
	for(int eid = head[now];eid != -1;eid = nid[eid]){
		if(!ansv.empty())return;
		int nxt = to[eid];
		//cerr<<now<<' '<<nxt<<":"<<idx[now]<<' '<<idx[nxt]<<endl;
		if(!idx[nxt]){
			up[nxt] = eid;
			par[nxt] = now;
			dfs(nxt,fa);
		}
		else{
			if(in[nxt]){
				getans(eid,now);
			}
		}
	}
	chain.pop_back();
	in[now] = false;
	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,0);
	if(!ansv.empty())return ansv;
	else return false;
}

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