Submission #1059838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059838		AmirAli_H1	Thousands Islands (IOI22_islands)	C++17	11.90 / 100	35 ms	24604 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> U, vector<int> V) {
	n = N; m = M;
	for (int i = 0; i < m; i++) {
		int u = U[i], v = V[i];
		adj[u].pb(Mp(v, i)); adjr[v].pb(Mp(u, i));
	}
	
	int vx = 0;
	fill(mark, mark + n, 0);
	while (len(adj[vx]) <= 1) {
		if (len(adj[vx]) == 0 || mark[vx]) return false;
		mark[vx] = 1; vx = adj[vx][0].F;
	}
	
	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 (mark[u] || mark[v]) continue;
		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[vx]) {
		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:88:18: warning: unused variable 'j' [-Wunused-variable]
   88 |     int u = f.F, j = f.S;
      |                  ^
islands.cpp:97:16: warning: unused variable 'j' [-Wunused-variable]
   97 |   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