Submission #1059907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059907		AmirAli_H1	Thousands Islands (IOI22_islands)	C++17	19.25 / 100	1093 ms	25428 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); D[i] = 0;
		}
	}
	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;
		}
		qu.push(vx); D[vx] = 0;
		fix_vc(); vx = ux;
	}
	return true;
}

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:95:17: warning: unused variable 'j' [-Wunused-variable]
   95 |    int u = f.F, j = f.S;
      |                 ^

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