# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1075913 | 2024-08-26T09:45:06 Z | NeroZein | Simurgh (IOI17_simurgh) | C++17 | 558 ms | 604 KB |
#include "simurgh.h" #include <bits/stdc++.h> using namespace std; vector<int> find_roads(int n, vector<int> eu, vector<int> ev) { int cc; vector<int> p(n), sz(n); function<int(int)> get = [&](int v) { return p[v] = (p[v] == v ? v : get(p[v])); }; auto unite = [&](int u, int v) { u = get(u); v = get(v); if (u == v) { return false; } if (sz[u] > sz[v]) { swap(u, v); } --cc; p[u] = v; sz[v] += sz[u]; return true; }; auto init_dsu = [&]() { cc = n; iota(p.begin(), p.end(), 0); fill(sz.begin(), sz.end(), 1); }; int m = (int) eu.size(); for (int i = 0; i < (1 << m); ++i) { init_dsu(); bool ok = true; vector<int> in_tree; for (int j = 0; j < m; ++j) { if (i >> j & 1) { in_tree.push_back(j); ok &= unite(eu[j], ev[j]); } } if (cc > 1 || !ok) { continue; } assert(in_tree.size() == n - 1); if (count_common_roads(in_tree) == n - 1) { return in_tree; } } assert(false); } //~ int common = count_common_roads(r);
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 41 ms | 344 KB | correct |
2 | Correct | 432 ms | 408 KB | correct |
3 | Correct | 558 ms | 408 KB | correct |
4 | Correct | 2 ms | 600 KB | correct |
5 | Correct | 0 ms | 360 KB | correct |
6 | Correct | 9 ms | 432 KB | correct |
7 | Correct | 0 ms | 348 KB | correct |
8 | Correct | 0 ms | 348 KB | correct |
9 | Correct | 0 ms | 348 KB | correct |
10 | Correct | 2 ms | 348 KB | correct |
11 | Correct | 0 ms | 348 KB | correct |
12 | Correct | 5 ms | 432 KB | correct |
13 | Correct | 136 ms | 344 KB | correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 41 ms | 344 KB | correct |
2 | Correct | 432 ms | 408 KB | correct |
3 | Correct | 558 ms | 408 KB | correct |
4 | Correct | 2 ms | 600 KB | correct |
5 | Correct | 0 ms | 360 KB | correct |
6 | Correct | 9 ms | 432 KB | correct |
7 | Correct | 0 ms | 348 KB | correct |
8 | Correct | 0 ms | 348 KB | correct |
9 | Correct | 0 ms | 348 KB | correct |
10 | Correct | 2 ms | 348 KB | correct |
11 | Correct | 0 ms | 348 KB | correct |
12 | Correct | 5 ms | 432 KB | correct |
13 | Correct | 136 ms | 344 KB | correct |
14 | Runtime error | 4 ms | 604 KB | Execution killed with signal 6 |
15 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 41 ms | 344 KB | correct |
2 | Correct | 432 ms | 408 KB | correct |
3 | Correct | 558 ms | 408 KB | correct |
4 | Correct | 2 ms | 600 KB | correct |
5 | Correct | 0 ms | 360 KB | correct |
6 | Correct | 9 ms | 432 KB | correct |
7 | Correct | 0 ms | 348 KB | correct |
8 | Correct | 0 ms | 348 KB | correct |
9 | Correct | 0 ms | 348 KB | correct |
10 | Correct | 2 ms | 348 KB | correct |
11 | Correct | 0 ms | 348 KB | correct |
12 | Correct | 5 ms | 432 KB | correct |
13 | Correct | 136 ms | 344 KB | correct |
14 | Runtime error | 4 ms | 604 KB | Execution killed with signal 6 |
15 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | correct |
2 | Runtime error | 4 ms | 348 KB | Execution killed with signal 6 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 41 ms | 344 KB | correct |
2 | Correct | 432 ms | 408 KB | correct |
3 | Correct | 558 ms | 408 KB | correct |
4 | Correct | 2 ms | 600 KB | correct |
5 | Correct | 0 ms | 360 KB | correct |
6 | Correct | 9 ms | 432 KB | correct |
7 | Correct | 0 ms | 348 KB | correct |
8 | Correct | 0 ms | 348 KB | correct |
9 | Correct | 0 ms | 348 KB | correct |
10 | Correct | 2 ms | 348 KB | correct |
11 | Correct | 0 ms | 348 KB | correct |
12 | Correct | 5 ms | 432 KB | correct |
13 | Correct | 136 ms | 344 KB | correct |
14 | Runtime error | 4 ms | 604 KB | Execution killed with signal 6 |
15 | Halted | 0 ms | 0 KB | - |