// In the name of Allah
#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 500 + 7;
int n, m;
vector<int> adj[maxn];
int mark[maxn], par[maxn];
int markx[maxn], M[maxn][maxn];
int ind[maxn][maxn], markw[maxn];
vector<int> res, ls, lsx, vc;
void dfs(int v) {
markw[v] = 1;
for (int u : adj[v]) {
if (!markw[u]) {
ls.pb(ind[v][u]);
dfs(u);
}
}
}
bool okx(int v) {
ls.clear();
for (int i = 0; i < n; i++) markw[i] = mark[i];
markw[v] = 1;
dfs(0); int T = -len(ls);
for (int u = 0; u < n; u++) {
if (u == v) continue;
if (mark[u]) ls.pb(ind[u][par[u]]);
else T++;
}
return (T == 1);
}
void checkx(int v) {
int t = 0, j = -1;
for (int u = 0; u < n; u++) {
if (mark[u]) continue;
if (M[v][u]) {
t++; j = u;
}
}
if (t == 1) {
par[v] = j;
mark[v] = 1;
}
}
void check(int v) {
if (!markx[v] && okx(v)) {
bool flag = 0;
int mx = -1; vc.clear();
for (int u : adj[v]) {
if (mark[u] || (markx[u] && flag)) continue;
lsx.clear(); lsx = ls;
lsx.pb(ind[u][v]);
int R = count_common_roads(lsx);
if (R > mx) {
mx = R;
vc.clear(); vc.pb(u);
}
else if (R == mx) vc.pb(u);
if (markx[u]) flag = 1;
}
for (int u : vc) M[v][u] = M[u][v] = 1;
markx[v] = 1;
}
if (markx[v]) checkx(v);
}
vector<int> find_roads(int Nx, vector<int> ux, vector<int> vx) {
n = Nx; m = len(ux);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) ind[i][j] = -1;
}
for (int i = 0; i < m; i++) {
int u = ux[i], v = vx[i];
adj[u].pb(v); adj[v].pb(u);
ind[u][v] = ind[v][u] = i;
}
while (true) {
int T = 0;
for (int v = 1; v < n; v++) {
if (!mark[v]) {
check(v);
T += 1;
}
}
if (T == 0) break;
}
for (int v = 1; v < n; v++) {
int u = par[v];
res.pb(ind[u][v]);
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
correct |
| 2 |
Correct |
0 ms |
348 KB |
correct |
| 3 |
Correct |
1 ms |
348 KB |
correct |
| 4 |
Correct |
0 ms |
348 KB |
correct |
| 5 |
Correct |
1 ms |
344 KB |
correct |
| 6 |
Correct |
0 ms |
348 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 |
0 ms |
348 KB |
correct |
| 11 |
Correct |
1 ms |
344 KB |
correct |
| 12 |
Correct |
0 ms |
348 KB |
correct |
| 13 |
Correct |
1 ms |
348 KB |
correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
correct |
| 2 |
Correct |
0 ms |
348 KB |
correct |
| 3 |
Correct |
1 ms |
348 KB |
correct |
| 4 |
Correct |
0 ms |
348 KB |
correct |
| 5 |
Correct |
1 ms |
344 KB |
correct |
| 6 |
Correct |
0 ms |
348 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 |
0 ms |
348 KB |
correct |
| 11 |
Correct |
1 ms |
344 KB |
correct |
| 12 |
Correct |
0 ms |
348 KB |
correct |
| 13 |
Correct |
1 ms |
348 KB |
correct |
| 14 |
Execution timed out |
3095 ms |
600 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
correct |
| 2 |
Correct |
0 ms |
348 KB |
correct |
| 3 |
Correct |
1 ms |
348 KB |
correct |
| 4 |
Correct |
0 ms |
348 KB |
correct |
| 5 |
Correct |
1 ms |
344 KB |
correct |
| 6 |
Correct |
0 ms |
348 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 |
0 ms |
348 KB |
correct |
| 11 |
Correct |
1 ms |
344 KB |
correct |
| 12 |
Correct |
0 ms |
348 KB |
correct |
| 13 |
Correct |
1 ms |
348 KB |
correct |
| 14 |
Execution timed out |
3095 ms |
600 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
correct |
| 2 |
Execution timed out |
3044 ms |
348 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
correct |
| 2 |
Correct |
0 ms |
348 KB |
correct |
| 3 |
Correct |
1 ms |
348 KB |
correct |
| 4 |
Correct |
0 ms |
348 KB |
correct |
| 5 |
Correct |
1 ms |
344 KB |
correct |
| 6 |
Correct |
0 ms |
348 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 |
0 ms |
348 KB |
correct |
| 11 |
Correct |
1 ms |
344 KB |
correct |
| 12 |
Correct |
0 ms |
348 KB |
correct |
| 13 |
Correct |
1 ms |
348 KB |
correct |
| 14 |
Execution timed out |
3095 ms |
600 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
