Submission #1059793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059793		AmirAli_H1	Thousands Islands (IOI22_islands)	C++17	11.90 / 100	48 ms	24412 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 mark[maxn], col[maxn], c;
vector<int> ls[maxn], vc; bool ok[maxn];

void dfs(int v) {
	mark[v] = 1;
	for (auto f : adj[v]) {
		int u = f.F, j = f.S;
		if (!mark[u]) dfs(u);
	}
	vc.pb(v);
}

void dfsr(int v) {
	mark[v] = 1;
	col[v] = c; ls[c].pb(v);
	for (auto f : adjr[v]) {
		int u = f.F, j = f.S;
		if (!mark[u]) dfsr(u);
	}
}

void scc() {
	fill(mark, mark + n, 0); vc.clear();
	for (int i = 0; i < n; i++) {
		if (!mark[i]) dfs(i);
	}
	reverse(all(vc));
	
	fill(mark, mark + n, 0); c = 0;
	for (int i : vc) {
		if (!mark[i]) {
			dfsr(i); c++;
		}
	}
}

variant<bool, vector<int>> find_journey(int N, int M, vector<int> ux, vector<int> vx) {
	n = N; m = M;
	for (int i = 0; i < m; i++) {
		int u = ux[i], v = vx[i];
		adj[u].pb(Mp(v, i)); adjr[v].pb(Mp(u, i));
	}
	
	scc();
	for (int i = c - 1; i >= 0; i--) {
		ok[i] = (len(ls[i]) >= 2);
		for (int v : ls[i]) {
			for (auto f : adj[v]) {
				int u = f.F, j = f.S;
				if (col[u] == col[v]) continue;
				ok[i] |= ok[col[u]];
			}
		}
	}
	
	int t = 0;
	for (auto f : adj[0]) {
		int u = f.F, j = f.S;
		if (ok[col[u]]) t++;
	}
	return (t >= 2);
}

Compilation message (stderr)

islands.cpp: In function 'void dfs(int)':
islands.cpp:30:16: warning: unused variable 'j' [-Wunused-variable]
   30 |   int u = f.F, j = f.S;
      |                ^
islands.cpp: In function 'void dfsr(int)':
islands.cpp:40:16: warning: unused variable 'j' [-Wunused-variable]
   40 |   int u = f.F, j = f.S;
      |                ^
islands.cpp: In function 'std::variant<bool, std::vector<int, std::allocator<int> > > find_journey(int, int, std::vector<int>, std::vector<int>)':
islands.cpp:72:18: warning: unused variable 'j' [-Wunused-variable]
   72 |     int u = f.F, j = f.S;
      |                  ^
islands.cpp:81:16: warning: unused variable 'j' [-Wunused-variable]
   81 |   int u = f.F, j = f.S;
      |                ^

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