| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 642050 |
2022-09-18T10:57:01 Z |
piOOE |
Simurgh (IOI17_simurgh) |
C++17 |
|
1 ms |
340 KB |
#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
void my_assert(bool f) {
if (!f) {
cerr << "228\n";
int x = 1337;
while (!f) {
x *= 2;
cerr << "yay";
}
}
}
struct dsu {
vector<int> p;
dsu(int n = 0) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
int get(int x) {
while (x != p[x]) x = p[x] = p[p[x]];
return x;
}
bool same(int x, int y) {
return get(x) == get(y);
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) {
return false;
}
p[y] = x;
return true;
}
};
vector<int> find_roads(int n, std::vector<int> U, std::vector<int> V) {
if (U.size() != n * (n - 1) / 2) {
vector<pair<int, int>> par(n);
vector<int> tin(n), tout(n);
int T = 0, ans_st = 0;
auto calc = [&](vector<int> st) {
T = 0;
ans_st = count_common_roads(st);
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < n - 1; ++i) {
g[U[st[i]]].emplace_back(V[st[i]], i);
g[V[st[i]]].emplace_back(U[st[i]], i);
}
function<void(int)> dfs = [&](int v) {
tin[v] = T++;
for (auto [to, i]: g[v]) {
if (to != par[v].first) {
par[to] = {v, i};
dfs(to);
}
}
tout[v] = T;
};
dfs(0);
};
int m = U.size();
dsu d(n);
vector<int> st;
vector<bool> in_st(m);
for (int i = 0; i < m; ++i) {
in_st[i] = d.unite(U[i], V[i]);
if (in_st[i]) {
st.push_back(i);
}
}
auto isp = [&](int x, int y) {
return tin[x] <= tin[y] && tout[x] >= tout[y];
};
auto path = [&](int x, int y) -> vector<int> {
int y_ = y, x_ = x;
vector<int> ans;
while (!isp(x, y_)) {
ans.push_back(par[x].second);
x = par[x].first;
}
while (!isp(y, x_)) {
ans.push_back(par[y].second);
y = par[y].first;
}
return ans;
};
calc(st);
vector<bool> sure(m);
for (int i = 0; i < m; ++i) {
if (find(st.begin(), st.end(), i) == st.end()) {
vector<int> now = path(U[i], V[i]);
vector<int> vis;
bool yay = false;
for (int j: now) {
if (!sure[st[j]]) {
auto q = st;
q.erase(q.begin() + j);
q.push_back(i);
int val = count_common_roads(q);
if (val > ans_st) {
st = q;
sure[i] = true;
calc(st);
yay = true;
break;
} else if (val < ans_st) {
sure[st[j]] = true;
break;
} else {
vis.push_back(st[j]);
}
}
}
if (yay) {
for (int j: vis) {
sure[j] = true;
}
} else {
if (!vis.empty()) {
for (int j: vis) {
auto it = find(st.begin(), st.end(), j);
if (it != st.end()) {
st.erase(it);
}
}
dsu s(n);
for (int j: st) {
assert(s.unite(U[j], V[j]));
}
for (int j = i + 1; j < m; ++j) {
if (s.unite(U[j], V[j])) {
st.push_back(j);
}
}
calc(st);
}
}
}
}
return st;
} else {
vector a(n, vector<int>(n, -1)), id(n, vector<int>(n));
const int m = n * (n - 1) / 2;
for (int i = 0; i < m; ++i) {
id[U[i]][V[i]] = id[V[i]][U[i]] = i;
}
vector<int> cnt(n), left(n);
for (int i = 0; i < n; ++i) {
vector<int> q;
for (int j = 0; j < n; ++j) {
if (j != i) {
q.push_back(id[i][j]);
}
}
cnt[i] = count_common_roads(q);
}
vector<int> ans;
vector<bool> used(n);
for (int iter = 0; iter < n; ++iter) {
int v = -1;
for (int i = 0; i < n; ++i) {
if (!used[i] && (v == -1 || left[v] > left[i])) {
v = i;
}
}
used[v] = true;
int chosen = -1;
if (left[v] != 0) {
assert(left[v] == 1);
vector<int> c;
for (int to = 0; to < n; ++to) {
if (to != v && a[v][to] == -1) {
c.push_back(id[v][to]);
}
}
while (c.size() != 1) {
int wait = c.size() & 1 ? c.back() : -1;
if (c.size() & 1) {
c.pop_back();
}
int sz = c.size() >> 1;
vector<int> st;
vector<bool> in_c(n);
for (int x: c) {
in_c[x] = true;
}
for (int to = 0; to < n; ++to) {
if (to != v && !in_c[to]) {
st.push_back(id[v][to]);
}
}
for (int i = 0; i < sz; ++i) {
st.push_back(id[c[i]][c[i + sz]]);
}
vector<int> L(st);
for (int i = 0; i < sz; ++i) {
L.push_back(id[v][c[i]]);
}
vector<int> R(st);
for (int i = sz; i < sz * 2; ++i) {
R.push_back(id[v][c[i]]);
}
int cntL = count_common_roads(L), cntR = count_common_roads(R);
if (cntL == cntR) {
assert(wait != -1);
c.clear();
} else if (cntL < cntR) {
c.erase(c.begin(), c.begin() + sz);
} else {
c.resize(sz);
}
if (wait != -1) {
c.push_back(wait);
}
}
assert(!c.empty());
chosen = c[0];
ans.push_back(id[v][chosen]);
}
for (int to = 0; to < n; ++to) {
if (to != v && a[v][to] == -1) {
if (to != chosen) {
a[v][to] = a[to][v] = 0;
} else {
a[v][to] = a[to][v] = 1;
}
}
}
}
}
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:46:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
46 | if (U.size() != n * (n - 1) / 2) {
| ~~~~~~~~~^~~~~~~~~~~~~~~~~~
simurgh.cpp:249:1: warning: control reaches end of non-void function [-Wreturn-type]
249 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
