Submission #1059880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059880		AmirAli_H1	Thousands Islands (IOI22_islands)	C++17	11.90 / 100	50 ms	25376 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];
int D[maxn]; queue<int> qu;
 
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++;
		}
	}
}

void del(int v) {
	for (auto f : adjr[v]) {
		int u = f.F, j = f.S;
		D[u]--;
		if (D[u] == 0) qu.push(u);
	}
}

void fix_vc() {
	while (!qu.empty()) {
		int v = qu.front(); qu.pop();
		del(v);
	}
}
 
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);
	}
	fix_vc();
	
	int vx = 0;
	while (D[vx] <= 1) {
		if (D[vx] == 0) return false;
		int ux = -1;
		for (auto f : adj[vx]) {
			int u = f.F, j = f.S;
			if (D[u] != 0) ux = u;
		}
		del(vx); fix_vc();
		vx = ux;
	}
	
	fill(mark, mark + n, 0);
	for (int i = 0; i < n; i++) {
		if (D[i] == 0) mark[i] = 1;
	}
	
	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:31:16: warning: unused variable 'j' [-Wunused-variable]
   31 |   int u = f.F, j = f.S;
      |                ^
islands.cpp: In function 'void dfsr(int)':
islands.cpp:41:16: warning: unused variable 'j' [-Wunused-variable]
   41 |   int u = f.F, j = f.S;
      |                ^
islands.cpp: In function 'void del(int)':
islands.cpp:63:16: warning: unused variable 'j' [-Wunused-variable]
   63 |   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:93:17: warning: unused variable 'j' [-Wunused-variable]
   93 |    int u = f.F, j = f.S;
      |                 ^
islands.cpp:119:18: warning: unused variable 'j' [-Wunused-variable]
  119 |     int u = f.F, j = f.S;
      |                  ^
islands.cpp:128:16: warning: unused variable 'j' [-Wunused-variable]
  128 |   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