Submission #627310

#	Time	Username	Problem	Language	Result	Execution time	Memory
627310		happypotato	Thousands Islands (IOI22_islands)	C++17	0 / 100	16 ms	16120 KiB

islands

#include "islands.h"
#include <variant>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
// global
int n, m;
const int mxN = 1e5 + 1;
vector<int> adj[mxN], opp[mxN];
bool vis[mxN];
void resetvis() {
	for (int i = 0; i < n; i++) vis[i] = false;
}
map<pii, vector<int> > mp, newmp;
int par[mxN];
int vispos[mxN];
vector<int> path;
int loopstart = -1;
void dupcycledfs(int u = 0, int pp = -1) {
	vis[u] = true;
	par[u] = pp;
	vispos[u] = path.size();
	path.pb(u);
	for (int v : adj[u]) {
		if (!vis[v]) {
			dupcycledfs(v, u);
		} else {
			int child = path[vispos[v] + 1];
			if (mp[{v, child}].size() >= 2) {
				loopstart = v;
				return;
			}
		}
	}
	path.pop_back();
	vispos[u] = -1;
}
vector<int> order;
void SCCDFS1(int u = 0) {
	vis[u] = true;
	for (int v : adj[u]) {
		if (!vis[v]) SCCDFS1(v);
	}
	order.pb(u);
}
int rep[mxN];
bool iscycle[mxN];
void SCCDFS2(int u, int tar) {
	vis[u] = true;
	rep[u] = tar;
	for (int v : opp[u]) {
		if (!vis[v]) {
			SCCDFS2(v, tar);
			iscycle[tar] = true;
		}
	}
}
vector<pair<int, bool> > newadj[mxN];
int come[mxN];
int cycleno = -1;
void dfs1(int u = 0, bool dupedge = false) {
	if (cycleno != -1) return;
	vis[u] = true;
	for (pair<int, bool> v : newadj[u]) {
		come[v.ff] += (!dupedge ? 1 : 2);
		if (come[v.ff] >= 2 && iscycle[v.ff]) {
			cycleno = v.ff;
			return;
		}
		if (!vis[v.ff]) {
			dfs1(v.ff, dupedge | v.ss);
		}
	}
}
vector<int> gencyclenode, gencycle;
bool gencycledfsdone = false;
void dfsgencycle(int u) {
	if (gencycledfsdone) return;
	vis[u] = true;
	gencyclenode.pb(u);
	for (int v : adj[u]) {
		if (!vis[v]) {
			dfsgencycle(v);
		} else if (v == rep[u]) {
			gencycledfsdone = true;
			return;
		}
	}
}
bool prevpathdone = false;
vector<int> godownpath[2];
void dfsfindpath(int u, bool dupedge) {
	vis[u] = true;
	for (pair<int, bool> v : newadj[u]) {

	}
}
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++) {
		mp[{U[i], V[i]}].pb(i);
		if (mp[{U[i], V[i]}].size() > 2) mp[{U[i], V[i]}].pop_back();
	}
	for (pair<pii, vector<int> > cur : mp) {
		adj[cur.ff.ff].pb(cur.ff.ss);
		opp[cur.ff.ss].pb(cur.ff.ff);
	}
	// check 2 edges in loop case
	dupcycledfs();
	resetvis();
	if (loopstart != -1) {
		vector<int> ans;
		int looppos = vispos[loopstart];
		for (int i = 0; i < int(path.size()) + 1; i++) {
			ans.pb(mp[{path[i], path[i + 1]}][0]);
		}
		ans.pb(mp[{path[looppos], path[looppos + 1]}][1]);
		ans.pb(mp[{path[looppos], path[looppos + 1]}][0]);
		for (int i = int(path.size()) - 2; i > looppos; i--) {
			ans.pb(mp[{path[i], path[i + 1]}][0]);
		}
		ans.pb(mp[{path[looppos], path[looppos + 1]}][1]);
		for (int i = looppos - 1; i >= 0; i--) {
			ans.pb(mp[{path[i], path[i + 1]}][0]);
		}
		return ans;
	}
	//
	SCCDFS1();
	reverse(order.begin(), order.end());
	resetvis();
	rep[0] = 0; vis[0] = true;
	for (int &u : order) {
		if (!vis[u]) {
			SCCDFS2(u, u);
		}
	}
	resetvis();
	for (int i = 0; i < m; i++) {
		if (!vis[U[i]] || !vis[V[i]]) continue;
		int nu = rep[U[i]], nv = rep[V[i]];
		if (nu == nv) continue;
		newmp[{nu, nv}].pb(i);
		if (newmp[{nu, nv}].size() > 2) newmp[{nu, nv}].pop_back();
	}
	for (pair<pii, vector<int> > cur : newmp) {
		newadj[cur.ff.ff].pb({cur.ff.ss, (cur.ss.size() == 2)});
	}
	dfs1();
	resetvis();
	if (cycleno == -1) return false;
	return true;
	for (int i = 0; i < n; i++) {
		vis[i] = (rep[i] != cycleno);
	}
	dfsgencycle(cycleno);
	for (int i = 1; i < int(gencyclenode.size()); i++) {
		gencycle.pb(mp[{gencyclenode[i - 1], gencyclenode[i]}][0]);
	}
	gencycle.pb(mp[{gencyclenode.back(), gencyclenode.front()}][0]);
	
}

Compilation message (stderr)

islands.cpp: In function 'void dfsfindpath(int, bool)':
islands.cpp:98:23: warning: variable 'v' set but not used [-Wunused-but-set-variable]
   98 |  for (pair<int, bool> v : newadj[u]) {
      |                       ^

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