#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '['; string sep = ""; for (const auto &x : v) os << sep << x, sep = ", "; return os << ']'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename A> ostream& operator<<(ostream &os, const set<A> &s) { os << '{'; string sep = ""; for (const auto &x : s) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const map<A, B> &m) { os << '{'; string sep = ""; for (const auto &x : m) os << sep << x.first << " -> " << x.second, sep = ", "; return os << '}'; }
void debug() { cerr << endl; }
template<typename Ini, typename... Fim> void debug(Ini I, Fim... F) { cerr << I; if(sizeof...(F)) cerr << ", "; debug(F...);}
#define db(...) cerr << "DEBUG (" << #__VA_ARGS__ << ") == ", debug(__VA_ARGS__)
using pii = pair<int,int>;
#define pb push_back
#define ff first
#define ss second
#define sz(a) (int)(a.size())
constexpr int maxn = 510;
struct Edge
{
int a, b, w, id; bool vis;
friend ostream& operator<<(ostream& os, const Edge& e) {
return os << e.vis;
// return os << e.a << ' ' << e.b << " == " << e.w;
// return os << e.a << ' ' << e.b << ' ' << e.w << ' ' << e.id << ' ' << e.vis;
}
};
vector<Edge> arvore;
int n, m, t;
int depth[maxn];
pii pai[maxn];
vector<pii> g[maxn], meus[maxn];
void dfs(int u) {
// db(u, depth[u]);
for(pii pp : g[u]) {
auto [v, id] = pp;
if(!depth[v]) {
depth[v] = depth[u] + 1;
arvore.pb({u, v, 0, id, 0});
pai[v] = {u, t++};
dfs(v);
}
else if(depth[v] > depth[u])
meus[u].push_back(pp);
}
}
void calc_tree() {
vector<int> qry(n-1);
for(int i = 0; i < t; i++)
qry[i] = arvore[i].id;
int base = count_common_roads(qry);
for(int u = 0; u < n; u++) {
if(!meus[u].size()) continue;
for(auto [v, id] : meus[u]) {
vector<int> ask, oto;
for(int i = v; i != u; i = pai[i].ff) {
int id_tree = pai[i].ss;
if(!arvore[id_tree].vis) ask.push_back(id_tree), arvore[id_tree].vis = 1;
else oto.push_back(id_tree);
}
if(!ask.size()) continue;
// assert(u != v);
// db(u, v);
// db(ask, oto);
if(oto.size()) {
int e = oto.front();
qry[e] = id;
int eu = abs(count_common_roads(qry) - base) ^ arvore[e].w;
qry[e] = arvore[e].id;
for(const int& e : ask) {
qry[e] = id;
arvore[e].w = abs(count_common_roads(qry) - base) ^ eu;
qry[e] = arvore[e].id;
}
} else {
vector<int> ans;
int mx = 0;
for(int e : ask) {
qry[e] = id;
ans.pb(count_common_roads(qry) - base), mx = max(mx, ans.back());
qry[e] = arvore[e].id;
}
int eu = mx;
for(int i = 0; i < sz(ask); i++) {
int e = ask[i];
arvore[e].w = eu ^ abs(ans[i]);
}
}
}
}
}
struct DSU
{
int pai[maxn], peso[maxn];
void init() { for(int i = 0; i < n; i++) pai[i] = i, peso[i] = 1; }
int find(int x) { return pai[x] == x ? x : pai[x] = find(pai[x]); }
bool join(int a, int b) {
a = find(a), b = find(b);
if(a == b) return 0;
if(peso[a] < peso[b]) swap(a, b);
pai[b] = a;
peso[a] += peso[b];
return 1;
}
} dsu;
pii edge[maxn*maxn];
int complete(vector<int>& base) {
// db(base);
dsu.init();
for(int x : base)
dsu.join(edge[x].ff, edge[x].ss);
int custo = 0;
for(Edge x : arvore)
if(dsu.join(x.a, x.b))
custo += x.w, base.pb(x.id);
// db(base, custo);
return custo;
}
vector<int> ans;
void solve(int u, int l, int r, int val) {
if(!val) return;
if(l == r) return (void)(ans.pb(meus[u][l].ss));
int m = (l+r) >> 1;
vector<int> gld;
for(int i = l; i <= m; i++)
gld.pb(meus[u][i].ss);
int b = complete(gld);
b = count_common_roads(gld) - b;
solve(u, l, m, b);
solve(u, m+1, r, val-b);
}
vector<int> find_roads(int N, vector<int> U, vector<int> V) {
// db(U, V);
n = N; m = (int)(U.size());
for(int i = 0; i < m; i++) {
g[U[i]].push_back({V[i], i});
g[V[i]].push_back({U[i], i});
edge[i] = {U[i], V[i]};
}
depth[0] = 1;
dfs(0);
calc_tree();
for(auto& e : arvore) {
e.w |= !e.vis;
if(e.w) ans.pb(e.id);
}
// db(sz(arvore), n);
// db(arvore);
for(int u = 0; u < n; u++) {
if(!meus[u].size()) continue;
vector<int> gld;
for(auto p : meus[u])
gld.pb(p.ss);
int b = complete(gld);
b = count_common_roads(gld) - b;
solve(u, 0, sz(meus[u])-1, b);
}
// db(ans);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
correct |
2 |
Correct |
1 ms |
332 KB |
correct |
3 |
Correct |
1 ms |
332 KB |
correct |
4 |
Correct |
1 ms |
332 KB |
correct |
5 |
Correct |
1 ms |
332 KB |
correct |
6 |
Correct |
1 ms |
332 KB |
correct |
7 |
Correct |
1 ms |
204 KB |
correct |
8 |
Correct |
1 ms |
332 KB |
correct |
9 |
Correct |
1 ms |
332 KB |
correct |
10 |
Correct |
1 ms |
332 KB |
correct |
11 |
Correct |
1 ms |
204 KB |
correct |
12 |
Correct |
1 ms |
332 KB |
correct |
13 |
Correct |
1 ms |
332 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
correct |
2 |
Correct |
1 ms |
332 KB |
correct |
3 |
Correct |
1 ms |
332 KB |
correct |
4 |
Correct |
1 ms |
332 KB |
correct |
5 |
Correct |
1 ms |
332 KB |
correct |
6 |
Correct |
1 ms |
332 KB |
correct |
7 |
Correct |
1 ms |
204 KB |
correct |
8 |
Correct |
1 ms |
332 KB |
correct |
9 |
Correct |
1 ms |
332 KB |
correct |
10 |
Correct |
1 ms |
332 KB |
correct |
11 |
Correct |
1 ms |
204 KB |
correct |
12 |
Correct |
1 ms |
332 KB |
correct |
13 |
Correct |
1 ms |
332 KB |
correct |
14 |
Correct |
2 ms |
332 KB |
correct |
15 |
Correct |
2 ms |
332 KB |
correct |
16 |
Correct |
2 ms |
332 KB |
correct |
17 |
Correct |
2 ms |
332 KB |
correct |
18 |
Correct |
1 ms |
332 KB |
correct |
19 |
Correct |
2 ms |
332 KB |
correct |
20 |
Correct |
2 ms |
332 KB |
correct |
21 |
Correct |
2 ms |
332 KB |
correct |
22 |
Correct |
1 ms |
332 KB |
correct |
23 |
Correct |
1 ms |
332 KB |
correct |
24 |
Correct |
1 ms |
332 KB |
correct |
25 |
Correct |
1 ms |
332 KB |
correct |
26 |
Correct |
1 ms |
332 KB |
correct |
27 |
Correct |
1 ms |
332 KB |
correct |
28 |
Correct |
1 ms |
328 KB |
correct |
29 |
Correct |
1 ms |
332 KB |
correct |
30 |
Correct |
2 ms |
332 KB |
correct |
31 |
Correct |
2 ms |
332 KB |
correct |
32 |
Correct |
1 ms |
332 KB |
correct |
33 |
Correct |
1 ms |
332 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
correct |
2 |
Correct |
1 ms |
332 KB |
correct |
3 |
Correct |
1 ms |
332 KB |
correct |
4 |
Correct |
1 ms |
332 KB |
correct |
5 |
Correct |
1 ms |
332 KB |
correct |
6 |
Correct |
1 ms |
332 KB |
correct |
7 |
Correct |
1 ms |
204 KB |
correct |
8 |
Correct |
1 ms |
332 KB |
correct |
9 |
Correct |
1 ms |
332 KB |
correct |
10 |
Correct |
1 ms |
332 KB |
correct |
11 |
Correct |
1 ms |
204 KB |
correct |
12 |
Correct |
1 ms |
332 KB |
correct |
13 |
Correct |
1 ms |
332 KB |
correct |
14 |
Correct |
2 ms |
332 KB |
correct |
15 |
Correct |
2 ms |
332 KB |
correct |
16 |
Correct |
2 ms |
332 KB |
correct |
17 |
Correct |
2 ms |
332 KB |
correct |
18 |
Correct |
1 ms |
332 KB |
correct |
19 |
Correct |
2 ms |
332 KB |
correct |
20 |
Correct |
2 ms |
332 KB |
correct |
21 |
Correct |
2 ms |
332 KB |
correct |
22 |
Correct |
1 ms |
332 KB |
correct |
23 |
Correct |
1 ms |
332 KB |
correct |
24 |
Correct |
1 ms |
332 KB |
correct |
25 |
Correct |
1 ms |
332 KB |
correct |
26 |
Correct |
1 ms |
332 KB |
correct |
27 |
Correct |
1 ms |
332 KB |
correct |
28 |
Correct |
1 ms |
328 KB |
correct |
29 |
Correct |
1 ms |
332 KB |
correct |
30 |
Correct |
2 ms |
332 KB |
correct |
31 |
Correct |
2 ms |
332 KB |
correct |
32 |
Correct |
1 ms |
332 KB |
correct |
33 |
Correct |
1 ms |
332 KB |
correct |
34 |
Correct |
42 ms |
2064 KB |
correct |
35 |
Correct |
43 ms |
1996 KB |
correct |
36 |
Correct |
33 ms |
1676 KB |
correct |
37 |
Correct |
8 ms |
332 KB |
correct |
38 |
Correct |
44 ms |
2056 KB |
correct |
39 |
Correct |
37 ms |
1892 KB |
correct |
40 |
Correct |
31 ms |
1684 KB |
correct |
41 |
Correct |
45 ms |
2048 KB |
correct |
42 |
Correct |
41 ms |
2056 KB |
correct |
43 |
Correct |
20 ms |
1320 KB |
correct |
44 |
Correct |
16 ms |
1124 KB |
correct |
45 |
Correct |
17 ms |
1208 KB |
correct |
46 |
Correct |
15 ms |
972 KB |
correct |
47 |
Correct |
18 ms |
588 KB |
correct |
48 |
Correct |
3 ms |
332 KB |
correct |
49 |
Correct |
6 ms |
332 KB |
correct |
50 |
Correct |
10 ms |
692 KB |
correct |
51 |
Correct |
18 ms |
1100 KB |
correct |
52 |
Correct |
16 ms |
1100 KB |
correct |
53 |
Correct |
15 ms |
1052 KB |
correct |
54 |
Correct |
18 ms |
1312 KB |
correct |
55 |
Correct |
20 ms |
1228 KB |
correct |
56 |
Correct |
20 ms |
1236 KB |
correct |
57 |
Correct |
22 ms |
1220 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
correct |
2 |
Correct |
1 ms |
332 KB |
correct |
3 |
Correct |
139 ms |
5448 KB |
correct |
4 |
Correct |
239 ms |
6780 KB |
correct |
5 |
Correct |
243 ms |
6812 KB |
correct |
6 |
Correct |
185 ms |
6756 KB |
correct |
7 |
Correct |
216 ms |
6692 KB |
correct |
8 |
Correct |
220 ms |
6696 KB |
correct |
9 |
Correct |
234 ms |
7692 KB |
correct |
10 |
Correct |
242 ms |
6840 KB |
correct |
11 |
Correct |
241 ms |
7364 KB |
correct |
12 |
Correct |
241 ms |
7620 KB |
correct |
13 |
Correct |
1 ms |
332 KB |
correct |
14 |
Correct |
224 ms |
7708 KB |
correct |
15 |
Correct |
238 ms |
6724 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
correct |
2 |
Correct |
1 ms |
332 KB |
correct |
3 |
Correct |
1 ms |
332 KB |
correct |
4 |
Correct |
1 ms |
332 KB |
correct |
5 |
Correct |
1 ms |
332 KB |
correct |
6 |
Correct |
1 ms |
332 KB |
correct |
7 |
Correct |
1 ms |
204 KB |
correct |
8 |
Correct |
1 ms |
332 KB |
correct |
9 |
Correct |
1 ms |
332 KB |
correct |
10 |
Correct |
1 ms |
332 KB |
correct |
11 |
Correct |
1 ms |
204 KB |
correct |
12 |
Correct |
1 ms |
332 KB |
correct |
13 |
Correct |
1 ms |
332 KB |
correct |
14 |
Correct |
2 ms |
332 KB |
correct |
15 |
Correct |
2 ms |
332 KB |
correct |
16 |
Correct |
2 ms |
332 KB |
correct |
17 |
Correct |
2 ms |
332 KB |
correct |
18 |
Correct |
1 ms |
332 KB |
correct |
19 |
Correct |
2 ms |
332 KB |
correct |
20 |
Correct |
2 ms |
332 KB |
correct |
21 |
Correct |
2 ms |
332 KB |
correct |
22 |
Correct |
1 ms |
332 KB |
correct |
23 |
Correct |
1 ms |
332 KB |
correct |
24 |
Correct |
1 ms |
332 KB |
correct |
25 |
Correct |
1 ms |
332 KB |
correct |
26 |
Correct |
1 ms |
332 KB |
correct |
27 |
Correct |
1 ms |
332 KB |
correct |
28 |
Correct |
1 ms |
328 KB |
correct |
29 |
Correct |
1 ms |
332 KB |
correct |
30 |
Correct |
2 ms |
332 KB |
correct |
31 |
Correct |
2 ms |
332 KB |
correct |
32 |
Correct |
1 ms |
332 KB |
correct |
33 |
Correct |
1 ms |
332 KB |
correct |
34 |
Correct |
42 ms |
2064 KB |
correct |
35 |
Correct |
43 ms |
1996 KB |
correct |
36 |
Correct |
33 ms |
1676 KB |
correct |
37 |
Correct |
8 ms |
332 KB |
correct |
38 |
Correct |
44 ms |
2056 KB |
correct |
39 |
Correct |
37 ms |
1892 KB |
correct |
40 |
Correct |
31 ms |
1684 KB |
correct |
41 |
Correct |
45 ms |
2048 KB |
correct |
42 |
Correct |
41 ms |
2056 KB |
correct |
43 |
Correct |
20 ms |
1320 KB |
correct |
44 |
Correct |
16 ms |
1124 KB |
correct |
45 |
Correct |
17 ms |
1208 KB |
correct |
46 |
Correct |
15 ms |
972 KB |
correct |
47 |
Correct |
18 ms |
588 KB |
correct |
48 |
Correct |
3 ms |
332 KB |
correct |
49 |
Correct |
6 ms |
332 KB |
correct |
50 |
Correct |
10 ms |
692 KB |
correct |
51 |
Correct |
18 ms |
1100 KB |
correct |
52 |
Correct |
16 ms |
1100 KB |
correct |
53 |
Correct |
15 ms |
1052 KB |
correct |
54 |
Correct |
18 ms |
1312 KB |
correct |
55 |
Correct |
20 ms |
1228 KB |
correct |
56 |
Correct |
20 ms |
1236 KB |
correct |
57 |
Correct |
22 ms |
1220 KB |
correct |
58 |
Correct |
1 ms |
332 KB |
correct |
59 |
Correct |
1 ms |
332 KB |
correct |
60 |
Correct |
139 ms |
5448 KB |
correct |
61 |
Correct |
239 ms |
6780 KB |
correct |
62 |
Correct |
243 ms |
6812 KB |
correct |
63 |
Correct |
185 ms |
6756 KB |
correct |
64 |
Correct |
216 ms |
6692 KB |
correct |
65 |
Correct |
220 ms |
6696 KB |
correct |
66 |
Correct |
234 ms |
7692 KB |
correct |
67 |
Correct |
242 ms |
6840 KB |
correct |
68 |
Correct |
241 ms |
7364 KB |
correct |
69 |
Correct |
241 ms |
7620 KB |
correct |
70 |
Correct |
1 ms |
332 KB |
correct |
71 |
Correct |
224 ms |
7708 KB |
correct |
72 |
Correct |
238 ms |
6724 KB |
correct |
73 |
Correct |
1 ms |
332 KB |
correct |
74 |
Correct |
245 ms |
7832 KB |
correct |
75 |
Correct |
237 ms |
7544 KB |
correct |
76 |
Correct |
96 ms |
3104 KB |
correct |
77 |
Correct |
244 ms |
7700 KB |
correct |
78 |
Correct |
250 ms |
7620 KB |
correct |
79 |
Correct |
239 ms |
7580 KB |
correct |
80 |
Correct |
246 ms |
7564 KB |
correct |
81 |
Correct |
167 ms |
6760 KB |
correct |
82 |
Correct |
235 ms |
7544 KB |
correct |
83 |
Correct |
151 ms |
4276 KB |
correct |
84 |
Correct |
106 ms |
5228 KB |
correct |
85 |
Correct |
99 ms |
4804 KB |
correct |
86 |
Correct |
69 ms |
3164 KB |
correct |
87 |
Correct |
54 ms |
2500 KB |
correct |
88 |
Correct |
46 ms |
1952 KB |
correct |
89 |
Correct |
47 ms |
1896 KB |
correct |
90 |
Correct |
42 ms |
1700 KB |
correct |
91 |
Correct |
20 ms |
460 KB |
correct |
92 |
Correct |
11 ms |
332 KB |
correct |
93 |
Correct |
91 ms |
4780 KB |
correct |
94 |
Correct |
68 ms |
3220 KB |
correct |
95 |
Correct |
65 ms |
3240 KB |
correct |
96 |
Correct |
45 ms |
1868 KB |
correct |
97 |
Correct |
47 ms |
1868 KB |
correct |
98 |
Correct |
53 ms |
2600 KB |
correct |
99 |
Correct |
47 ms |
1964 KB |
correct |
100 |
Correct |
37 ms |
792 KB |
correct |
101 |
Correct |
12 ms |
468 KB |
correct |
102 |
Correct |
110 ms |
4108 KB |
correct |
103 |
Correct |
110 ms |
4152 KB |
correct |
104 |
Correct |
112 ms |
4040 KB |
correct |
105 |
Correct |
107 ms |
3972 KB |
correct |