| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1084564 | SamueleVid | Rarest Insects (IOI22_insects) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
// constexpr int MAXN = 1e5 + 5;
constexpr int MAXN = 1e3 + 5;
constexpr int MAXM = 2e5 + 5;
// vector<pair<int, int>> adj[MAXN]; // nodo, barca
vector<int> adj[MAXN][MAXN];
bool v[MAXN];
vector<int> barche;
vector<int> barche_res;
vector<int> nodi;
int N;
bool fatto = false;
variant<bool, vector<int>> n_two(int N, int M, vector<int> U, vector<int> V) {
vector<int> el_primo;
vector<int> el_secondo;
for (int i = 0; i < M; i ++) {
if (U[i] == 0) el_primo.push_back(i);
if (U[i] == 1) el_secondo.push_back(i);
}
if (el_primo.size() >= 2 && el_secondo.size() >= 1) {
int a = el_primo[0];
int b = el_secondo[0];
int c = el_primo[1];
vector<int> res = {a, b, c, a, b, c};
return res;
}
return false;
}
variant<bool, vector<int>> subtask_two(int N, int M, vector<int> U, vector<int> V) {
int a, b, c, d, e, f;
for (int i = 0; i < M; i ++) {
if (U[i] == 0 && V[i] == 1) a = i;
if (U[i] == 1 && V[i] == 0) b = i;
if (U[i] == 1 && V[i] == 2) c = i;
if (U[i] == 2 && V[i] == 1) d = i;
if (U[i] == 2 && V[i] == 0) e = i;
if (U[i] == 0 && V[i] == 2) f = i;
}
vector<int> res = {a, c, e, f, d, b, e, c, a, b, d, f};
return res;
}
void dfs(int u) {
if (fatto) return;
// cout << "sono a u " << u << '\n';
nodi.push_back(u);
if (v[u]) {
// cout << "trovato ciclo !!" << '\n';
// minchia ora comincia il bello
int primo_u = -1;
for (int i = 0; i < nodi.size(); i ++) {
if (nodi[i] == u) {
primo_u = i;
break;
}
}
// assert(primo_u != -1);
// cout << "primo u " << u << " -> " << primo_u << '\n';
// for (int i = 0; i < N; i ++) {
// for (int j = 0; j < N; j ++) {
// cout << "Barche da " << i << " a " << j << " : ";
// for (auto x : adj[i][j]) cout << (char)(x + 'A') << " ";
// cout << '\n';
// }
// }
// cout << "Nodi : " << '\n';
// for (auto x : nodi) cout << x << " ";
// cout << '\n';
// cout << "piroetta due volte" << '\n';
int prec = u;
vector<int> to_add_one, to_add_two;
// cout << "- prima volta" << '\n';
for (int i = nodi.size() - 2; i >= primo_u; i --) {
// cout << "i, nodo : " << i << " " << nodi[i] << '\n';
if (adj[prec][nodi[i]].size() == 0) exit(-1);
int barca = adj[prec][nodi[i]].back(); adj[prec][nodi[i]].pop_back();
// cout << "visito " << nodi[i] << " con barca " << (char)(barca + 'A') << '\n';
adj[nodi[i]][prec].push_back(barca);
to_add_two.push_back(barca);
prec = nodi[i];
}
// cout << "- seconda volta" << '\n';
for (int i = nodi.size() - 2; i >= primo_u; i --) {
// cout << "i, nodo : " << i << " " << nodi[i] << '\n';
int barca = adj[prec][nodi[i]].back(); adj[prec][nodi[i]].pop_back();
// cout << "visito " << nodi[i] << " con barca " << (char)(barca + 'A') << '\n';
adj[nodi[i]][prec].push_back(barca);
to_add_one.push_back(barca);
prec = nodi[i];
}
for (auto x : to_add_one) barche.push_back(x);
for (auto x : to_add_two) barche.push_back(x);
// cout << "--- e ora piroetta normale " << '\n';
for (int i = primo_u + 1; i < nodi.size(); i ++) {
// cout << "i, nodo : " << i << " " << nodi[i] << '\n';
int barca = adj[prec][nodi[i]].back(); adj[prec][nodi[i]].pop_back();
// cout << "visito " << nodi[i] << " con barca " << (char)(barca + 'A') << '\n';
adj[nodi[i]][prec].push_back(barca);
barche.push_back(barca);
prec = nodi[i];
}
// cout << " e torno indietro " << '\n';
for (int i = primo_u - 1; i >= 0; i --) {
// cout << "vedo i, nodo : " << i << " " << nodi[i] << '\n';
int barca = adj[prec][nodi[i]].back(); adj[prec][nodi[i]].pop_back();
adj[nodi[i]][prec].push_back(barca);
// cout << "visito " << i << " con barca " << (char)(barca + 'A') << '\n';
barche.push_back(barca);
prec = nodi[i];
}
barche_res = barche;
fatto = true;
return;
}
if (fatto) return;
v[u] = 1;
for (int i = 0; i < N; i ++) {
if (nodi.size() >= 2 && nodi[nodi.size() - 2] == i) continue;
if (adj[u][i].empty()) continue;
int barca = adj[u][i].back(); adj[u][i].pop_back();
adj[i][u].push_back(barca);
// cout << "vado da " << i << " e prendo barca " << (char)(barca + 'A') << '\n';
barche.push_back(barca);
dfs(i);
if (fatto) return;
barche.pop_back();
adj[i][u].pop_back();
adj[u][i].push_back(barca);
}
if (fatto) return;
v[u] = 0;
nodi.pop_back();
}
variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
:: N = N;
if (N <= 2) return n_two(N, M, U, V);
// if (N <= 400) return subtask_two(N, M, U, V);
fill(v, v + MAXN, 0);
for (int i = 0; i < MAXN; i ++) {
for (int j = 0; j < MAXN; j ++) adj[i][j] = vector<int>();
}
for (int i = 0; i < M; i ++) {
adj[U[i]][V[i]].push_back(i);
}
for (int i = 0; i < MAXN; i ++) {
for (int j = 0; j < MAXN; j ++) if (adj[i][j].size() > 1) exit(-1);
}
dfs(0);
if (fatto) return barche_res;
return false;
}