oj.uz

Submission #1080565

# Submission time Handle Problem Language Result Execution time Memory
1080565 2024-08-29T11:00:06 Z Joshua_Andersson Simurgh (IOI17_simurgh) C++14
100 / 100
 364 ms 22356 KB 
#include "simurgh.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll linf = ll(1e18);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)

#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

struct UF
{
	vi par;
	UF(int n) : par(n)
	{
		rep(i, n)par[i] = i;
	}
	int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
	void merge(int a, int b)
	{
		a = find(a); b = find(b);
		if (a == b) return;
		par[b] = a;
	}
};

vi spanning;
const int maxn = 500;
const int maxm = maxn * maxn;
int is_golden[maxm], vis[maxn], parnode[maxn], paredge[maxn];
int depth[maxn], visedge[maxm], maxup[maxn], known[maxm];

vector<p2> up_edges[maxn];
void dfs(int u, vector<vector<p2>>& edges)
{
	repe(e, edges[u])
	{
		if (vis[e.first]) // back edge
		{
			if (visedge[e.second]) continue;
			visedge[e.second] = 1;
			up_edges[u].push_back(e);
			maxup[u] = min(maxup[u], depth[e.first]);
		}
		else
		{
			depth[e.first] = depth[u] + 1;
			visedge[e.second] = 1;
			spanning.push_back(e.second);
			vis[e.first] = 1;
			parnode[e.first] = u;
			paredge[e.first] = e.second;
			dfs(e.first, edges);
			if (maxup[e.first]>=depth[e.first]) // bridge
			{
				is_golden[e.second] = 1;
				known[e.second] = 1;
			}
			maxup[u] = min(maxup[u], maxup[e.first]);
		}
	}
}

vi a, b;
int n;
int forest_query(vi edges)
{
	vi q;
	UF uf(n);
	repe(u, edges)
	{
		q.emplace_back(u);
		if (uf.find(a[u]) == uf.find(b[u])) assert(0);
		uf.merge(a[u], b[u]);
	}
	int num_good = 0;
	repe(s, spanning)
	{
		if (uf.find(a[s]) == uf.find(b[s])) continue;
		uf.merge(a[s], b[s]);
		num_good += is_golden[s];
		q.push_back(s);
	}
	assert(sz(q) < n);
	return count_common_roads(q) - num_good;
}

std::vector<int> find_roads(int N, std::vector<int> A, std::vector<int> B) {
	a = A;
	b = B;
	n = N;
	rep(i, maxn) maxup[i] = int(1e6);
	memset(is_golden, 0, sizeof(is_golden));
	memset(parnode, -1, sizeof(parnode));
	if (n==2)
	{
		return { 0 };
	}
	int m = sz(a);

	vector<vector<p2>> dedges(n);
	rep(i, m)
	{
		dedges[a[i]].emplace_back(b[i], i);
		dedges[b[i]].emplace_back(a[i], i);
	}
	vis[0] = 1;
	parnode[0] = 0;
	depth[0] = 0;
	dfs(0, dedges);
	parnode[0] = -1;
	repp(u, 1, n)
	{
		repe(e, up_edges[u])
		{
			vi cycle = { e.second };

			int num_unknown = 0;

			int v = u;
			while (v != 0 && v != e.first)
			{
				if (!known[paredge[v]]) num_unknown++;
				cycle.push_back(paredge[v]);
				v = parnode[v];
			}
			if (num_unknown == 0) continue;
			
			bool seen_known = 0;
			int mx = 0;
			vector<p2> res;
			rep(i, sz(cycle))
			{
				UF uf(n);
				vi q;
				rep(j, sz(cycle))
				{
					if (i == j) continue;
					q.push_back(cycle[j]);
					uf.merge(a[cycle[j]], b[cycle[j]]);
				}
				repe(u, spanning)
				{
					if (uf.find(a[u]) == uf.find(b[u])) continue;
					uf.merge(a[u], b[u]);
					q.push_back(u);
				}
				if (known[cycle[i]])
				{
					if (!seen_known)
					{
						seen_known = 1;
						int k = count_common_roads(q);
						if (!is_golden[cycle[i]])
						{
							mx = k;
						}
						else mx = k + 1;
					}
				}
				else
				{
					res.emplace_back(cycle[i], count_common_roads(q));
				}
				mx = max(mx, res.back().second);
			}
			
			repe(v, res)
			{
				if (v.second < mx)
				{
					is_golden[v.first] = 1;
				}
				known[v.first] = 1;
			}
		}
	}
	
	assert(sz(spanning) == n - 1);

	vector<set<int>> edges(n);
	rep(i, m)
	{
		edges[a[i]].insert(i);
		edges[b[i]].insert(i);
	}
	queue<int> leaf;
	vi deg(n);
	rep(i, n)
	{
		deg[i] = forest_query(vi(all(edges[i])));
		if (deg[i] == 1) leaf.push(i);
	}

	vi par(n, -1);
	while (sz(leaf))
	{
		int u = leaf.front();
		leaf.pop();

		if (deg[u] == 0) break;
		assert(deg[u] == 1);
		int lo = -1;
		int hi = sz(edges[u]);
		while (lo+1<hi)
		{
			int mid = (lo + hi) / 2;
			vi q;
			auto start = edges[u].begin();
			rep(i, mid + 1)
			{
				q.push_back(*start);
				start++;
			}
			if (forest_query(q))
			{
				hi = mid;
			}
			else lo = mid;
		}
		auto start = edges[u].begin();
		rep(i, hi) start = next(start);
		int e = *start;
		int v = a[e] == u ? b[e] : a[e];
		edges[v].erase(e);
		deg[v]--;
		if (deg[v]==1)
		{
			leaf.push(v);
		}
		par[u] = e;
	}

	vi r;
	rep(i, n) if (par[i] != -1)r.push_back(par[i]);
	int common = count_common_roads(r);
	assert(common == n - 1);
	return r;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB correct
2 Correct 1 ms 3164 KB correct
3 Correct 1 ms 3164 KB correct
4 Correct 1 ms 3164 KB correct
5 Correct 1 ms 3160 KB correct
6 Correct 1 ms 3164 KB correct
7 Correct 1 ms 3164 KB correct
8 Correct 1 ms 3164 KB correct
9 Correct 1 ms 3164 KB correct
10 Correct 1 ms 3164 KB correct
11 Correct 1 ms 3164 KB correct
12 Correct 1 ms 3164 KB correct
13 Correct 1 ms 3164 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB correct
2 Correct 1 ms 3164 KB correct
3 Correct 1 ms 3164 KB correct
4 Correct 1 ms 3164 KB correct
5 Correct 1 ms 3160 KB correct
6 Correct 1 ms 3164 KB correct
7 Correct 1 ms 3164 KB correct
8 Correct 1 ms 3164 KB correct
9 Correct 1 ms 3164 KB correct
10 Correct 1 ms 3164 KB correct
11 Correct 1 ms 3164 KB correct
12 Correct 1 ms 3164 KB correct
13 Correct 1 ms 3164 KB correct
14 Correct 2 ms 3420 KB correct
15 Correct 2 ms 3420 KB correct
16 Correct 2 ms 3440 KB correct
17 Correct 2 ms 3420 KB correct
18 Correct 1 ms 3164 KB correct
19 Correct 2 ms 3420 KB correct
20 Correct 2 ms 3164 KB correct
21 Correct 3 ms 3404 KB correct
22 Correct 2 ms 3164 KB correct
23 Correct 2 ms 3164 KB correct
24 Correct 1 ms 3164 KB correct
25 Correct 1 ms 3164 KB correct
26 Correct 2 ms 3344 KB correct
27 Correct 2 ms 3164 KB correct
28 Correct 1 ms 3164 KB correct
29 Correct 1 ms 3164 KB correct
30 Correct 2 ms 3164 KB correct
31 Correct 2 ms 3164 KB correct
32 Correct 2 ms 3164 KB correct
33 Correct 2 ms 3164 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB correct
2 Correct 1 ms 3164 KB correct
3 Correct 1 ms 3164 KB correct
4 Correct 1 ms 3164 KB correct
5 Correct 1 ms 3160 KB correct
6 Correct 1 ms 3164 KB correct
7 Correct 1 ms 3164 KB correct
8 Correct 1 ms 3164 KB correct
9 Correct 1 ms 3164 KB correct
10 Correct 1 ms 3164 KB correct
11 Correct 1 ms 3164 KB correct
12 Correct 1 ms 3164 KB correct
13 Correct 1 ms 3164 KB correct
14 Correct 2 ms 3420 KB correct
15 Correct 2 ms 3420 KB correct
16 Correct 2 ms 3440 KB correct
17 Correct 2 ms 3420 KB correct
18 Correct 1 ms 3164 KB correct
19 Correct 2 ms 3420 KB correct
20 Correct 2 ms 3164 KB correct
21 Correct 3 ms 3404 KB correct
22 Correct 2 ms 3164 KB correct
23 Correct 2 ms 3164 KB correct
24 Correct 1 ms 3164 KB correct
25 Correct 1 ms 3164 KB correct
26 Correct 2 ms 3344 KB correct
27 Correct 2 ms 3164 KB correct
28 Correct 1 ms 3164 KB correct
29 Correct 1 ms 3164 KB correct
30 Correct 2 ms 3164 KB correct
31 Correct 2 ms 3164 KB correct
32 Correct 2 ms 3164 KB correct
33 Correct 2 ms 3164 KB correct
34 Correct 58 ms 7348 KB correct
35 Correct 49 ms 7164 KB correct
36 Correct 46 ms 6236 KB correct
37 Correct 19 ms 3352 KB correct
38 Correct 49 ms 7256 KB correct
39 Correct 53 ms 6952 KB correct
40 Correct 41 ms 6236 KB correct
41 Correct 53 ms 7504 KB correct
42 Correct 51 ms 7260 KB correct
43 Correct 27 ms 5468 KB correct
44 Correct 26 ms 4896 KB correct
45 Correct 25 ms 5208 KB correct
46 Correct 23 ms 4700 KB correct
47 Correct 15 ms 3928 KB correct
48 Correct 6 ms 3164 KB correct
49 Correct 10 ms 3356 KB correct
50 Correct 15 ms 3928 KB correct
51 Correct 33 ms 5208 KB correct
52 Correct 28 ms 4952 KB correct
53 Correct 22 ms 4696 KB correct
54 Correct 33 ms 5468 KB correct
55 Correct 34 ms 5212 KB correct
56 Correct 31 ms 5332 KB correct
57 Correct 28 ms 5212 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB correct
2 Correct 1 ms 3164 KB correct
3 Correct 172 ms 15224 KB correct
4 Correct 329 ms 21332 KB correct
5 Correct 310 ms 21588 KB correct
6 Correct 310 ms 21332 KB correct
7 Correct 300 ms 21332 KB correct
8 Correct 323 ms 21328 KB correct
9 Correct 333 ms 21428 KB correct
10 Correct 334 ms 21420 KB correct
11 Correct 294 ms 21328 KB correct
12 Correct 320 ms 21432 KB correct
13 Correct 1 ms 3164 KB correct
14 Correct 307 ms 21408 KB correct
15 Correct 332 ms 21188 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB correct
2 Correct 1 ms 3164 KB correct
3 Correct 1 ms 3164 KB correct
4 Correct 1 ms 3164 KB correct
5 Correct 1 ms 3160 KB correct
6 Correct 1 ms 3164 KB correct
7 Correct 1 ms 3164 KB correct
8 Correct 1 ms 3164 KB correct
9 Correct 1 ms 3164 KB correct
10 Correct 1 ms 3164 KB correct
11 Correct 1 ms 3164 KB correct
12 Correct 1 ms 3164 KB correct
13 Correct 1 ms 3164 KB correct
14 Correct 2 ms 3420 KB correct
15 Correct 2 ms 3420 KB correct
16 Correct 2 ms 3440 KB correct
17 Correct 2 ms 3420 KB correct
18 Correct 1 ms 3164 KB correct
19 Correct 2 ms 3420 KB correct
20 Correct 2 ms 3164 KB correct
21 Correct 3 ms 3404 KB correct
22 Correct 2 ms 3164 KB correct
23 Correct 2 ms 3164 KB correct
24 Correct 1 ms 3164 KB correct
25 Correct 1 ms 3164 KB correct
26 Correct 2 ms 3344 KB correct
27 Correct 2 ms 3164 KB correct
28 Correct 1 ms 3164 KB correct
29 Correct 1 ms 3164 KB correct
30 Correct 2 ms 3164 KB correct
31 Correct 2 ms 3164 KB correct
32 Correct 2 ms 3164 KB correct
33 Correct 2 ms 3164 KB correct
34 Correct 58 ms 7348 KB correct
35 Correct 49 ms 7164 KB correct
36 Correct 46 ms 6236 KB correct
37 Correct 19 ms 3352 KB correct
38 Correct 49 ms 7256 KB correct
39 Correct 53 ms 6952 KB correct
40 Correct 41 ms 6236 KB correct
41 Correct 53 ms 7504 KB correct
42 Correct 51 ms 7260 KB correct
43 Correct 27 ms 5468 KB correct
44 Correct 26 ms 4896 KB correct
45 Correct 25 ms 5208 KB correct
46 Correct 23 ms 4700 KB correct
47 Correct 15 ms 3928 KB correct
48 Correct 6 ms 3164 KB correct
49 Correct 10 ms 3356 KB correct
50 Correct 15 ms 3928 KB correct
51 Correct 33 ms 5208 KB correct
52 Correct 28 ms 4952 KB correct
53 Correct 22 ms 4696 KB correct
54 Correct 33 ms 5468 KB correct
55 Correct 34 ms 5212 KB correct
56 Correct 31 ms 5332 KB correct
57 Correct 28 ms 5212 KB correct
58 Correct 1 ms 3164 KB correct
59 Correct 1 ms 3164 KB correct
60 Correct 172 ms 15224 KB correct
61 Correct 329 ms 21332 KB correct
62 Correct 310 ms 21588 KB correct
63 Correct 310 ms 21332 KB correct
64 Correct 300 ms 21332 KB correct
65 Correct 323 ms 21328 KB correct
66 Correct 333 ms 21428 KB correct
67 Correct 334 ms 21420 KB correct
68 Correct 294 ms 21328 KB correct
69 Correct 320 ms 21432 KB correct
70 Correct 1 ms 3164 KB correct
71 Correct 307 ms 21408 KB correct
72 Correct 332 ms 21188 KB correct
73 Correct 1 ms 3160 KB correct
74 Correct 299 ms 21216 KB correct
75 Correct 318 ms 20768 KB correct
76 Correct 111 ms 10064 KB correct
77 Correct 304 ms 22096 KB correct
78 Correct 364 ms 22100 KB correct
79 Correct 320 ms 22356 KB correct
80 Correct 302 ms 21584 KB correct
81 Correct 283 ms 19544 KB correct
82 Correct 282 ms 21708 KB correct
83 Correct 178 ms 12880 KB correct
84 Correct 158 ms 14824 KB correct
85 Correct 149 ms 13648 KB correct
86 Correct 102 ms 10308 KB correct
87 Correct 90 ms 8520 KB correct
88 Correct 78 ms 7264 KB correct
89 Correct 70 ms 6864 KB correct
90 Correct 68 ms 6440 KB correct
91 Correct 35 ms 3672 KB correct
92 Correct 24 ms 3420 KB correct
93 Correct 146 ms 13648 KB correct
94 Correct 108 ms 10316 KB correct
95 Correct 114 ms 10160 KB correct
96 Correct 71 ms 6492 KB correct
97 Correct 75 ms 7248 KB correct
98 Correct 93 ms 8516 KB correct
99 Correct 77 ms 7372 KB correct
100 Correct 45 ms 4280 KB correct
101 Correct 27 ms 3420 KB correct
102 Correct 177 ms 12896 KB correct
103 Correct 149 ms 12884 KB correct
104 Correct 161 ms 12668 KB correct
105 Correct 160 ms 12628 KB correct