#include "simurgh.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 500;
vector<pii> adj[MAXN + 10]; // { node, edge id }
struct Tree {
set<int> edge;
int par[MAXN + 10];
int dep[MAXN + 10];
int peid[MAXN + 10];
vector<int> get_edges() {
vector<int> ids;
for(auto &i:edge) ids.eb(i);
return ids;
}
int query() {
// cerr << "query:";
// out();
return count_common_roads(get_edges());
}
void dfs(int x, int p, int d, int pe, bool tree_edge_only = true) {
par[x] = p;
dep[x] = d;
peid[x] = pe;
for(auto &i:adj[x]) if(i.F != p && dep[i.F] == 0) {
if(tree_edge_only && !edge.count(i.S)) continue;
else if(!tree_edge_only) edge.insert(i.S);
dfs(i.F, x, d + 1, i.S, tree_edge_only);
}
}
void add_edge(int a, int b, int id) {
if(edge.count(id)) return;
// cerr << "tree: \n";
// For(i, 0, 3) cerr << par[i] << " \n"[i == 3];
// For(i, 0, 3) cerr << peid[i] << " \n"[i == 3];
memset(dep, 0, sizeof(dep));
dfs(0, -1, 1, -1);
int cnt = query();
while(a != b) {
if(dep[a] < dep[b]) swap(a, b);
int id2 = peid[a];
edge.erase(id2);
edge.insert(id);
// cerr << id2 << " -> " << id << "?\n";
if(query() > cnt) return;
edge.erase(id);
edge.insert(id2);
a = par[a];
}
}
void out() {
for(auto &i:get_edges()) {
cerr << i << " ";
}
cerr << "\n";
}
} tr;
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
int M = sz(U);
For(i, 0, M - 1) {
adj[U[i]].eb(V[i], i);
adj[V[i]].eb(U[i], i);
}
tr.dfs(0, -1, 1, -1, false);
// tr.out();
For(i, 0, M - 1) {
tr.add_edge(U[i], V[i], i);
// tr.out();
}
return tr.get_edges();
// vector<int> r(n - 1);
// for(int i = 0; i < n - 1; i++)
// r[i] = i;
// int common = count_common_roads(r);
// if(common == n - 1)
// return r;
// r[0] = n - 1;
// return r;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
correct |
2 |
Correct |
1 ms |
212 KB |
correct |
3 |
Correct |
1 ms |
212 KB |
correct |
4 |
Correct |
0 ms |
212 KB |
correct |
5 |
Correct |
1 ms |
324 KB |
correct |
6 |
Correct |
0 ms |
212 KB |
correct |
7 |
Correct |
1 ms |
212 KB |
correct |
8 |
Correct |
0 ms |
212 KB |
correct |
9 |
Correct |
0 ms |
212 KB |
correct |
10 |
Correct |
1 ms |
324 KB |
correct |
11 |
Correct |
0 ms |
212 KB |
correct |
12 |
Correct |
0 ms |
312 KB |
correct |
13 |
Correct |
0 ms |
320 KB |
correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
correct |
2 |
Correct |
1 ms |
212 KB |
correct |
3 |
Correct |
1 ms |
212 KB |
correct |
4 |
Correct |
0 ms |
212 KB |
correct |
5 |
Correct |
1 ms |
324 KB |
correct |
6 |
Correct |
0 ms |
212 KB |
correct |
7 |
Correct |
1 ms |
212 KB |
correct |
8 |
Correct |
0 ms |
212 KB |
correct |
9 |
Correct |
0 ms |
212 KB |
correct |
10 |
Correct |
1 ms |
324 KB |
correct |
11 |
Correct |
0 ms |
212 KB |
correct |
12 |
Correct |
0 ms |
312 KB |
correct |
13 |
Correct |
0 ms |
320 KB |
correct |
14 |
Correct |
35 ms |
340 KB |
correct |
15 |
Correct |
27 ms |
384 KB |
correct |
16 |
Correct |
29 ms |
340 KB |
correct |
17 |
Correct |
24 ms |
380 KB |
correct |
18 |
Correct |
6 ms |
340 KB |
correct |
19 |
Correct |
25 ms |
324 KB |
correct |
20 |
Correct |
20 ms |
380 KB |
correct |
21 |
Correct |
19 ms |
372 KB |
correct |
22 |
Correct |
9 ms |
340 KB |
correct |
23 |
Correct |
8 ms |
340 KB |
correct |
24 |
Correct |
7 ms |
340 KB |
correct |
25 |
Correct |
1 ms |
316 KB |
correct |
26 |
Correct |
7 ms |
340 KB |
correct |
27 |
Correct |
8 ms |
340 KB |
correct |
28 |
Correct |
3 ms |
340 KB |
correct |
29 |
Correct |
1 ms |
212 KB |
correct |
30 |
Correct |
9 ms |
340 KB |
correct |
31 |
Correct |
10 ms |
340 KB |
correct |
32 |
Correct |
9 ms |
340 KB |
correct |
33 |
Correct |
9 ms |
320 KB |
correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
correct |
2 |
Correct |
1 ms |
212 KB |
correct |
3 |
Correct |
1 ms |
212 KB |
correct |
4 |
Correct |
0 ms |
212 KB |
correct |
5 |
Correct |
1 ms |
324 KB |
correct |
6 |
Correct |
0 ms |
212 KB |
correct |
7 |
Correct |
1 ms |
212 KB |
correct |
8 |
Correct |
0 ms |
212 KB |
correct |
9 |
Correct |
0 ms |
212 KB |
correct |
10 |
Correct |
1 ms |
324 KB |
correct |
11 |
Correct |
0 ms |
212 KB |
correct |
12 |
Correct |
0 ms |
312 KB |
correct |
13 |
Correct |
0 ms |
320 KB |
correct |
14 |
Correct |
35 ms |
340 KB |
correct |
15 |
Correct |
27 ms |
384 KB |
correct |
16 |
Correct |
29 ms |
340 KB |
correct |
17 |
Correct |
24 ms |
380 KB |
correct |
18 |
Correct |
6 ms |
340 KB |
correct |
19 |
Correct |
25 ms |
324 KB |
correct |
20 |
Correct |
20 ms |
380 KB |
correct |
21 |
Correct |
19 ms |
372 KB |
correct |
22 |
Correct |
9 ms |
340 KB |
correct |
23 |
Correct |
8 ms |
340 KB |
correct |
24 |
Correct |
7 ms |
340 KB |
correct |
25 |
Correct |
1 ms |
316 KB |
correct |
26 |
Correct |
7 ms |
340 KB |
correct |
27 |
Correct |
8 ms |
340 KB |
correct |
28 |
Correct |
3 ms |
340 KB |
correct |
29 |
Correct |
1 ms |
212 KB |
correct |
30 |
Correct |
9 ms |
340 KB |
correct |
31 |
Correct |
10 ms |
340 KB |
correct |
32 |
Correct |
9 ms |
340 KB |
correct |
33 |
Correct |
9 ms |
320 KB |
correct |
34 |
Incorrect |
203 ms |
1548 KB |
WA in grader: NO |
35 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
correct |
2 |
Correct |
0 ms |
212 KB |
correct |
3 |
Incorrect |
104 ms |
3912 KB |
WA in grader: NO |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
correct |
2 |
Correct |
1 ms |
212 KB |
correct |
3 |
Correct |
1 ms |
212 KB |
correct |
4 |
Correct |
0 ms |
212 KB |
correct |
5 |
Correct |
1 ms |
324 KB |
correct |
6 |
Correct |
0 ms |
212 KB |
correct |
7 |
Correct |
1 ms |
212 KB |
correct |
8 |
Correct |
0 ms |
212 KB |
correct |
9 |
Correct |
0 ms |
212 KB |
correct |
10 |
Correct |
1 ms |
324 KB |
correct |
11 |
Correct |
0 ms |
212 KB |
correct |
12 |
Correct |
0 ms |
312 KB |
correct |
13 |
Correct |
0 ms |
320 KB |
correct |
14 |
Correct |
35 ms |
340 KB |
correct |
15 |
Correct |
27 ms |
384 KB |
correct |
16 |
Correct |
29 ms |
340 KB |
correct |
17 |
Correct |
24 ms |
380 KB |
correct |
18 |
Correct |
6 ms |
340 KB |
correct |
19 |
Correct |
25 ms |
324 KB |
correct |
20 |
Correct |
20 ms |
380 KB |
correct |
21 |
Correct |
19 ms |
372 KB |
correct |
22 |
Correct |
9 ms |
340 KB |
correct |
23 |
Correct |
8 ms |
340 KB |
correct |
24 |
Correct |
7 ms |
340 KB |
correct |
25 |
Correct |
1 ms |
316 KB |
correct |
26 |
Correct |
7 ms |
340 KB |
correct |
27 |
Correct |
8 ms |
340 KB |
correct |
28 |
Correct |
3 ms |
340 KB |
correct |
29 |
Correct |
1 ms |
212 KB |
correct |
30 |
Correct |
9 ms |
340 KB |
correct |
31 |
Correct |
10 ms |
340 KB |
correct |
32 |
Correct |
9 ms |
340 KB |
correct |
33 |
Correct |
9 ms |
320 KB |
correct |
34 |
Incorrect |
203 ms |
1548 KB |
WA in grader: NO |
35 |
Halted |
0 ms |
0 KB |
- |