| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1094408 |
2024-09-29T15:01:14 Z |
mat_jur |
Village (BOI20_village) |
C++17 |
|
48 ms |
16172 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
void dfs(int v, int p, vector<int> &match, const vector<vector<int>> &g) {
for (int u : g[v]) {
if (u == p) continue;
dfs(u, v, match, g);
}
if (match[v] != -1) return;
for (int u : g[v]) {
if (match[u] == -1) {
match[v] = u;
match[u] = v;
}
}
}
vector<int> matching(const vector<vector<int>> &g) {
int n = ssize(g);
vector<int> match(n, -1);
dfs(0, -1, match, g);
return match;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> g(n);
for (int i = 0; i < n-1; ++i) {
int u, v;
cin >> u >> v;
g[u-1].eb(v-1);
g[v-1].eb(u-1);
}
vector<int> match = matching(g);
int mn = n;
for (int v = 0; v < n; ++v) {
if (match[v] != -1) continue;
mn++;
int u = g[v][0];
match[v] = match[u];
match[u] = v;
}
cout << mn << ' ' << mn << '\n';
for (int x : match) cout << x+1 << ' ';
cout << '\n';
for (int x : match) cout << x+1 << ' ';
cout << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 2 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 3 |
Correct |
0 ms |
452 KB |
Output is correct |
| 4 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 5 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 6 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 7 |
Correct |
0 ms |
456 KB |
Output is correct |
| 8 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 9 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 10 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 11 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 12 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 13 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 16 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 17 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 2 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 3 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 4 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 5 |
Partially correct |
1 ms |
344 KB |
Partially correct |
| 6 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 7 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 8 |
Partially correct |
1 ms |
344 KB |
Partially correct |
| 9 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 10 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 11 |
Partially correct |
1 ms |
344 KB |
Partially correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 14 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 15 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 16 |
Partially correct |
1 ms |
600 KB |
Partially correct |
| 17 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 18 |
Partially correct |
1 ms |
492 KB |
Partially correct |
| 19 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 20 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 21 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 22 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 23 |
Partially correct |
1 ms |
344 KB |
Partially correct |
| 24 |
Partially correct |
1 ms |
344 KB |
Partially correct |
| 25 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 26 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 27 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 28 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 29 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 30 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 2 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 3 |
Correct |
0 ms |
452 KB |
Output is correct |
| 4 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 5 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 6 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 7 |
Correct |
0 ms |
456 KB |
Output is correct |
| 8 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 9 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 10 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 11 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 12 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 13 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 16 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 17 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 18 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 19 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 20 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 21 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 22 |
Partially correct |
1 ms |
344 KB |
Partially correct |
| 23 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 24 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 25 |
Partially correct |
1 ms |
344 KB |
Partially correct |
| 26 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 27 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 28 |
Partially correct |
1 ms |
344 KB |
Partially correct |
| 29 |
Correct |
1 ms |
348 KB |
Output is correct |
| 30 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 31 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 32 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 33 |
Partially correct |
1 ms |
600 KB |
Partially correct |
| 34 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 35 |
Partially correct |
1 ms |
492 KB |
Partially correct |
| 36 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 37 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 38 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 39 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 40 |
Partially correct |
1 ms |
344 KB |
Partially correct |
| 41 |
Partially correct |
1 ms |
344 KB |
Partially correct |
| 42 |
Partially correct |
0 ms |
348 KB |
Partially correct |
| 43 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 44 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 45 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 46 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 47 |
Partially correct |
1 ms |
348 KB |
Partially correct |
| 48 |
Partially correct |
32 ms |
8028 KB |
Partially correct |
| 49 |
Partially correct |
38 ms |
8648 KB |
Partially correct |
| 50 |
Partially correct |
35 ms |
8788 KB |
Partially correct |
| 51 |
Partially correct |
25 ms |
6744 KB |
Partially correct |
| 52 |
Partially correct |
34 ms |
8540 KB |
Partially correct |
| 53 |
Partially correct |
34 ms |
7764 KB |
Partially correct |
| 54 |
Partially correct |
23 ms |
8020 KB |
Partially correct |
| 55 |
Partially correct |
48 ms |
16172 KB |
Partially correct |
| 56 |
Partially correct |
42 ms |
12108 KB |
Partially correct |
| 57 |
Partially correct |
41 ms |
10836 KB |
Partially correct |
| 58 |
Partially correct |
39 ms |
9804 KB |
Partially correct |
| 59 |
Partially correct |
35 ms |
8784 KB |
Partially correct |
| 60 |
Correct |
26 ms |
8916 KB |
Output is correct |
| 61 |
Partially correct |
28 ms |
9128 KB |
Partially correct |
| 62 |
Partially correct |
34 ms |
8968 KB |
Partially correct |
| 63 |
Partially correct |
38 ms |
8636 KB |
Partially correct |
| 64 |
Partially correct |
33 ms |
9040 KB |
Partially correct |
| 65 |
Partially correct |
35 ms |
9052 KB |
Partially correct |
| 66 |
Partially correct |
35 ms |
8540 KB |
Partially correct |
| 67 |
Partially correct |
25 ms |
6608 KB |
Partially correct |
| 68 |
Partially correct |
31 ms |
7616 KB |
Partially correct |
| 69 |
Partially correct |
30 ms |
9104 KB |
Partially correct |
| 70 |
Partially correct |
46 ms |
8568 KB |
Partially correct |
| 71 |
Partially correct |
29 ms |
6472 KB |
Partially correct |
| 72 |
Partially correct |
28 ms |
7276 KB |
Partially correct |
| 73 |
Partially correct |
33 ms |
9112 KB |
Partially correct |
| 74 |
Partially correct |
39 ms |
8312 KB |
Partially correct |
| 75 |
Partially correct |
40 ms |
8596 KB |
Partially correct |
| 76 |
Partially correct |
35 ms |
8560 KB |
Partially correct |
| 77 |
Partially correct |
33 ms |
8668 KB |
Partially correct |
| 78 |
Partially correct |
29 ms |
6108 KB |
Partially correct |
| 79 |
Partially correct |
26 ms |
7004 KB |
Partially correct |
| 80 |
Partially correct |
39 ms |
8540 KB |
Partially correct |
| 81 |
Partially correct |
44 ms |
8764 KB |
Partially correct |
| 82 |
Partially correct |
33 ms |
8784 KB |
Partially correct |
