| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 249865 |
2020-07-16T07:37:32 Z |
srvlt |
Simurgh (IOI17_simurgh) |
C++14 |
|
1 ms |
640 KB |
#include "simurgh.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int n0 = 53, m0 = 1300;
int N, M, par[n0], used[n0], ch[m0], h[n0], common;
vector <int> g[n0], V, U, cur;
set <int> st1, st2;
void add(int x) {
st1.insert(x), st2.erase(x);
}
void del(int x) {
st1.erase(x), st2.insert(x);
}
void dfs(int v, bool flag) {
if (v == 0) par[v] = -1;
used[v] = 1;
for (int i : g[v]) {
int to = V[i] ^ U[i] ^ v;
if (used[to] || (flag && st1.find(i) == st1.end())) continue;
par[to] = i;
h[to] = h[v] + 1;
if (!flag)
add(i);
dfs(to, flag);
}
}
int ask() {
cur.clear();
for (int i : st1) cur.pb(i);
return count_common_roads(cur);
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
for (int i = 0; i < m0; i++) ch[i] = 2;
N = n, M = u.size(), V = v, U = u;
for (int i = 0; i < M; i++) {
g[v[i]].pb(i), g[u[i]].pb(i);
st2.insert(i);
}
dfs(0, false);
common = ask();
vector <int> path;
while (!st2.empty()) {
path.clear();
int i = *st2.begin();
int a = v[i], b = u[i];
if (h[a] > h[b]) swap(a, b);
int bad = 0;
while (b != a) {
if (par[b] == -1) {
st2.erase(i);
bad = 1;
break;
}
path.pb(par[b]);
b = v[par[b]] ^ u[par[b]] ^ b;
}
if (bad) continue;
add(i);
int ind = -1;
for (int j : path) {
if (ch[j] == 1) continue;
del(j);
int x = ask();
add(j);
if (x == common + 1) {
common++;
ch[i] = 1;
ind = j;
break;
}
}
if (ch[i] == 2) ch[i] = 3;
if (ch[i] == 1) {
assert(ind != -1);
ch[ind] = 3;
del(ind);
st2.erase(ind);
memset(& used, 0, sizeof(used));
dfs(0, true);
} else {
del(i);
st2.erase(i);
}
}
assert(ask() == n - 1);
return cur;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
correct |
| 2 |
Runtime error |
1 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
