Submission #1059939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059939		AmirAli_H1	Thousands Islands (IOI22_islands)	C++17	100 / 100	70 ms	24804 KiB

islands

// In the name of Allah

#include <bits/stdc++.h>
#include "islands.h"
using namespace std;

typedef		long long			ll;
typedef		pair<int, int>		pii;
typedef		pair<ll, ll>		pll;

#define		endl				'\n'
#define		sep					' '
#define		F					first
#define		S					second
#define		Mp					make_pair
#define		pb					push_back
#define		all(x)				(x).begin(),(x).end()
#define		len(x)				((ll) (x).size())

const int maxn = 2e5 + 7;

int n, m;
vector<pii> adj[maxn], adjr[maxn];
int D[maxn]; queue<int> qu;
int mark[maxn]; vector<int> E;
vector<int> res, vc;
int M[maxn], cnt;

void fix_vc() {
	while (!qu.empty()) {
		int v = qu.front(); qu.pop();
		for (auto f : adjr[v]) {
			int u = f.F, j = f.S;
			if (D[u] == 0) continue;
			else if (D[u] == 1) qu.push(u);
			D[u]--;
		}
	}
}

void checkx(int vx, int i) {
	int v = vx; mark[v] = 1;
	auto f = adj[v][i];
	v = f.F; E.pb(f.S);
	while (!mark[v]) {
		mark[v] = 1;
		auto f = adj[v][0];
		v = f.F; E.pb(f.S);
	}
}

int get_next(int v) {
	for (auto f : adj[v]) {
		int u = f.F, j = f.S;
		if (len(res) >= 1 && res.back() == j) continue;
		if (!M[j]) {
			M[j] = 1; cnt++;
			res.pb(j);
			return u;
		}
	}
	for (auto f : adjr[v]) {
		int u = f.F, j = f.S;
		if (len(res) >= 1 && res.back() == j) continue;
		if (M[j]) {
			M[j] = 0; cnt--;
			res.pb(j);
			return u;
		}
	}
	return -1;
}

void get_ans(int vx) {
	int v = vx;
	while (true) {
		v = get_next(v);
		if (v == vx && cnt == 0) return ;
	}
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
	n = N; m = M;
	for (int i = 0; i < m; i++) {
		int u = U[i], v = V[i]; D[u]++;
		adj[u].pb(Mp(v, i)); adjr[v].pb(Mp(u, i));
	}
	
	for (int i = 0; i < n; i++) {
		if (D[i] == 0) {
			qu.push(i); D[i] = 0;
		}
	}
	fix_vc();
	
	int vx = 0;
	while (D[vx] <= 1) {
		if (D[vx] == 0) return false;
		int ux = -1, i = -1;
		for (auto f : adj[vx]) {
			int u = f.F, j = f.S;
			if (D[u] != 0) {
				ux = u; i = j;
			}
		}
		vc.pb(i);
		qu.push(vx); D[vx] = 0;
		fix_vc(); vx = ux;
	}
	
	for (int i = 0; i < n; i++) {
		adj[i].clear(); adjr[i].clear();
	}
	for (int i = 0; i < m; i++) {
		int u = U[i], v = V[i];
		if (D[u] == 0 || D[v] == 0) continue;
		adj[u].pb(Mp(v, i)); adjr[v].pb(Mp(u, i));
	}
	
	for (int j : vc) res.pb(j);
	
	checkx(vx, 0); checkx(vx, 1);
	for (int i = 0; i < n; i++) {
		adj[i].clear(); adjr[i].clear();
	}
	for (int i : E) {
		int u = U[i], v = V[i];
		if (D[u] == 0 || D[v] == 0) continue;
		adj[u].pb(Mp(v, i)); adjr[v].pb(Mp(u, i));
	}
	get_ans(vx);
	
	reverse(all(vc));
	for (int j : vc) res.pb(j);
	
	return res;
}

Compilation message (stderr)

islands.cpp: In function 'void fix_vc()':
islands.cpp:33:17: warning: unused variable 'j' [-Wunused-variable]
   33 |    int u = f.F, j = f.S;
      |                 ^

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