| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 536043 |
2022-03-12T08:03:30 Z |
KoD |
Simurgh (IOI17_simurgh) |
C++17 |
|
1 ms |
468 KB |
#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
template <class F> struct rec_lambda : private F {
explicit rec_lambda(F&& f) : F(forward<F>(f)) {}
template <class... Args> decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, forward<Args>(args)...);
}
};
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
const int M = U.size();
vector<vector<int>> graph(N);
for (int i = 0; i < M; ++i) {
graph[U[i]].push_back(i);
graph[V[i]].push_back(i);
}
const auto dst = [&](const int u, const int e) {
return U[e] ^ V[e] ^ u;
};
vector<int> depth(N), pedge(N);
vector<char> is_tree(M);
depth[0] = 1;
rec_lambda([&](auto&& dfs, const int u) -> void {
for (const int e : graph[u]) {
const int v = dst(u, e);
if (depth[v] == 0) {
depth[v] = depth[u] + 1;
pedge[v] = e;
is_tree[e] = true;
dfs(v);
}
}
})(0);
for (int i = 0; i < M; ++i) {
if (depth[U[i]] > depth[V[i]]) swap(U[i], V[i]);
}
vector<int> ask_list;
ask_list.reserve(N - 1);
const auto ask_tree = [&] {
ask_list.clear();
for (int i = 0; i < M; ++i) {
if (is_tree[i]) ask_list.push_back(i);
}
return count_common_roads(ask_list);
};
const auto ask_swapped = [&](const int e, const int f) {
is_tree[e] = true;
is_tree[f] = false;
const int ret = ask_tree();
is_tree[e] = false;
is_tree[f] = true;
return ret;
};
const int base = ask_tree();
vector<int> type(M, -1);
for (int e = 0; e < M; ++e) {
if (is_tree[e]) continue;
vector<int> done, tbd;
for (int u = V[e]; u != U[e]; u = dst(u, pedge[u])) {
const int f = pedge[u];
(type[f] >= 0 ? done : tbd).push_back(f);
}
const int m = tbd.size();
if (m == 0) continue;
vector<int> dif(m);
for (int i = 0; i < m; ++i) {
dif[i] = ask_swapped(e, tbd[i]) - base;
}
if (done.empty()) {
for (const int x : dif) {
if (x == 1) type[e] = 1;
if (x == -1) type[e] = 0;
}
if (type[e] == -1) type[e] = 0;
} else {
const int f = done.front();
type[e] = type[f] + ask_swapped(e, f) - base;
}
for (int i = 0; i < m; ++i) {
type[tbd[i]] = type[e] - dif[i];
}
}
for (int i = 0; i < M; ++i) {
if (is_tree[i] and type[i] == -1) type[i] = 1;
}
vector<char> used(N);
const auto count = [&](vector<int> list) {
if (list.empty()) return 0;
ask_list.clear();
for (const int e : list) {
ask_list.push_back(e);
used[V[e]] = true;
}
int subt = 0;
for (int u = 1; u < N; ++u) {
if (!used[u]) {
const int e = pedge[u];
subt += type[e];
ask_list.push_back(e);
}
}
for (const int e : list) {
used[V[e]] = false;
}
assert(ask_list.size() == N - 1);
return count_common_roads(ask_list) - subt;
};
for (int pivot = 0; pivot < N; ++pivot) {
vector<int> list;
for (const int e : graph[pivot]) {
if (type[e] == -1) list.push_back(e);
}
rec_lambda([&](auto&& dfs, const int l, const int r) -> void {
if (count(vector<int>(list.begin() + l, list.begin() + r)) == 0) return;
if (l + 1 == r) {
type[list[l]] = 1;
} else {
const int m = (l + r) / 2;
dfs(l, m);
dfs(m, r);
}
})(0, list.size());
for (const int e : list) {
if (type[e] == -1) type[e] = 0;
}
}
vector<int> ret;
ret.reserve(N - 1);
for (int i = 0; i < M; ++i) {
if (type[i] == 1) ret.push_back(i);
}
return ret;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from simurgh.cpp:1:
simurgh.cpp: In lambda function:
simurgh.cpp:107:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
107 | assert(ask_list.size() == N - 1);
| ~~~~~~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
