oj.uz

Submission #835001

# Submission time Handle Problem Language Result Execution time Memory
835001 2023-08-23T05:13:59 Z pavement Thousands Islands (IOI22_islands) C++17
22.75 / 100
 25 ms 5332 KB 
#include "islands.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define eb emplace_back

using ii = pair<int, int>;

vector<int> cyc, path, par;
vector<bool> vis;
vector<vector<ii> > adj, adj_t;

namespace ufds {
	vector<int> lnk, sz, num_edges;
	
	void init(int n) {
		lnk.resize(n);
		iota(lnk.begin(), lnk.end(), 0);
		sz.resize(n);
		fill(sz.begin(), sz.end(), 1);
		num_edges.resize(n);
		fill(num_edges.begin(), num_edges.end(), 0);
	}
	int find(int x) {
		if (x == lnk[x]) {
			return x;
		}
		return lnk[x] = find(lnk[x]);
	}
	void unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) {
			return;
		}
		if (sz[b] > sz[a]) {
			swap(a, b);
		}
		sz[a] += sz[b];
		num_edges[a] += num_edges[b];
		lnk[b] = a;
	}
};

int dfs(int u, int e = -1) {
	vis[u] = 1;
	for (auto [v, idx] : adj[u]) {
		if ((idx ^ 1) != e && vis[v]) {
			cyc.pb(idx);
			//~ cout << u << " --> " << v << endl;
			//~ cout << u << " RET " << v << endl;
			return v;
		}
	}
	for (auto [v, idx] : adj[u]) if ((idx ^ 1) != e) {
		int tmp = dfs(v, idx);
		if (tmp != -1) {
			if (tmp == -2) {
				path.pb(idx);
			} else {
				cyc.pb(idx);
				if (tmp == u) {
					tmp = -2;
				}
			}
			//~ cout << u << " RET " << tmp << endl;
			return tmp;
		}
	}
	//~ cout << u << " RET " << -1 << endl;
	return -1;
}

bool get_path(int u, int tar, int e = -1) {
	par[u] = e;
	if (u == tar) {
		return 1;
	}
	for (auto [v, idx] : adj_t[u]) if (v != e) {
		if (get_path(v, tar, u)) {
			path.pb(idx);
			return 1;
		}
	}
	return 0;
}

variant<bool, vector<int> > find_journey(int N, int M, vector<int> U, vector<int> V) {
	ufds::init(N);
	adj.resize(N);
	adj_t.resize(N);
	for (int i = 0; i < M; i++) {
		if (i % 2 == 0) {
			ufds::unite(U[i], V[i]);
			ufds::num_edges[ufds::find(U[i])]++;
		}
		adj[U[i]].eb(V[i], i);
	}
	if (ufds::num_edges[ufds::find(0)] != ufds::sz[ufds::find(0)] - 1) {
		vis.resize(N);
		dfs(0);
		reverse(path.begin(), path.end());
		reverse(cyc.begin(), cyc.end());
		vector<int> out;
		//~ cout << "HERE\n";
		for (int i : path) {
			out.pb(i);
		}
		for (int i : cyc) {
			out.pb(i);
		}
		reverse(cyc.begin(), cyc.end());
		for (int i : cyc) {
			out.pb(i ^ 1);
		}
		for (int i : cyc) {
			out.pb(i);
		}
		reverse(cyc.begin(), cyc.end());
		for (int i : cyc) {
			out.pb(i ^ 1);
		}
		reverse(cyc.begin(), cyc.end());
		reverse(path.begin(), path.end());
		for (int i : path) {
			out.pb(i);
		}
		return out;
	} else {
		vector<int> deg(N, 0);
		for (int i = 0; i < M; i++) {
			if (ufds::find(U[i]) == ufds::find(0)) {
				deg[U[i]]++;
			}
		}
		if (deg[0] > 1 || *max_element(deg.begin(), deg.end()) > 2) {
			if (deg[0] > 1) {
				vector<int> outgoing;
				for (int i = 0; i < M; i++) {
					if (U[i] == 0) {
						outgoing.pb(i);
					}
				}
				auto ret = {outgoing[0], outgoing[0] ^ 1, outgoing[1], outgoing[1] ^ 1, outgoing[0] ^ 1, outgoing[0], outgoing[1] ^ 1, outgoing[1]};
				return ret;
			} else {
				for (int i = 0; i < M; i++) {
					if (ufds::find(U[i]) == ufds::find(0)) {
						adj_t[U[i]].eb(V[i], i);
					}
				}
				par = vector<int>(N, -1);
				int node = max_element(deg.begin(), deg.end()) - deg.begin();
				get_path(0, node);
				vector<int> outgoing;
				for (auto [u, idx] : adj_t[node]) {
					if (u != par[node]) {
						outgoing.pb(idx);
					}
				}
				auto cyc = {outgoing[0], outgoing[0] ^ 1, outgoing[1], outgoing[1] ^ 1, outgoing[0] ^ 1, outgoing[0], outgoing[1] ^ 1, outgoing[1]};
				vector<int> ret;
				reverse(path.begin(), path.end());
				for (int i : path) {
					ret.pb(i);
				}
				for (int i : cyc) {
					ret.pb(i);
				}
				reverse(path.begin(), path.end());
				for (int i : path) {
					ret.pb(i);
				}
				assert((int)ret.size() <= (int)2e6);
				return ret;
			}
		} else {
			return false;
		}
	}
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
1.75 / 5.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 23 ms 4564 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 15 ms 3028 KB Output is correct
18 Correct 12 ms 2644 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 22 ms 4564 KB Output is correct

Subtask #4
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 1 ms 340 KB Output is partially correct
3 Partially correct 23 ms 4948 KB Output is partially correct
4 Partially correct 25 ms 5332 KB Output is partially correct
5 Partially correct 1 ms 340 KB Output is partially correct
6 Partially correct 1 ms 468 KB Output is partially correct
7 Partially correct 0 ms 212 KB Output is partially correct
8 Partially correct 0 ms 212 KB Output is partially correct
9 Partially correct 0 ms 212 KB Output is partially correct
10 Partially correct 1 ms 468 KB Output is partially correct
11 Incorrect 2 ms 468 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -