| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 656304 |
2022-11-06T21:36:33 Z |
esomer |
Village (BOI20_village) |
C++17 |
|
76 ms |
20172 KB |
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
const int MOD = 998244353;
vector<int> v;
int ans = 0;
bool DFS(int x, vector<vector<int>>& adj, int p){
vector<int> odd;
for(int node : adj[x]){
if(node == p) continue;
bool rep = DFS(node, adj, x);
if(rep) odd.push_back(node);
}
if(odd.size() == 0){
if(x == 0){
int node = adj[x][0];
if(v[v[node]] == node){
v[x] = v[node];
v[node] = x;
ans += 2;
}else{
int node1 = v[node];
int node2 = v[v[node]];
v[node1] = node2;
v[node2] = node1;
v[x] = node;
v[node] = x;
ans += 2;
}
}else return 1;
}else{
if(((int)odd.size()) % 2 == 1){
for(int i = 1; i < (int)odd.size() - 1; i += 2){
v[odd[i]] = odd[i + 1];
v[odd[i + 1]] = odd[i];
ans += 4;
}
v[x] = odd[0];
v[odd[0]] = x;
ans += 2;
}else{
for(int i = 2; i < (int)odd.size() - 1; i += 2){
v[odd[i]] = odd[i + 1];
v[odd[i + 1]] = odd[i];
ans += 4;
}
v[x] = odd[0];
v[odd[0]] = odd[1];
v[odd[1]] = x;
ans += 4;
}
}
return 0;
}
void solve(){
int n; cin >> n;
v.resize(n);
vector<vector<int>> adj(n);
for(int i = 0; i < n - 1; i++){
int a, b; cin >> a >> b; a--; b--;
adj[a].push_back(b); adj[b].push_back(a);
}
DFS(0, adj, -1);
cout << ans << " "<<-1 << endl;
for(int x : v) cout << x + 1 << " ";
cout << endl;
for(int i = 0; i < n; i++) cout << 1 << " ";
cout << endl;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("inpt.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
//int tt; cin >> tt;
int tt = 1;
for(int t = 1; t <= tt; t++){
//cout << "Case #"<<t << ": ";
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 2 |
Partially correct |
0 ms |
212 KB |
Partially correct |
| 3 |
Partially correct |
0 ms |
212 KB |
Partially correct |
| 4 |
Partially correct |
0 ms |
212 KB |
Partially correct |
| 5 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 6 |
Partially correct |
0 ms |
212 KB |
Partially correct |
| 7 |
Partially correct |
1 ms |
320 KB |
Partially correct |
| 8 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 9 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 10 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 11 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 12 |
Partially correct |
0 ms |
212 KB |
Partially correct |
| 13 |
Partially correct |
0 ms |
320 KB |
Partially correct |
| 14 |
Partially correct |
0 ms |
320 KB |
Partially correct |
| 15 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 16 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 17 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 2 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 3 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 4 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 5 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 6 |
Partially correct |
1 ms |
324 KB |
Partially correct |
| 7 |
Partially correct |
1 ms |
468 KB |
Partially correct |
| 8 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 9 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 10 |
Partially correct |
1 ms |
324 KB |
Partially correct |
| 11 |
Partially correct |
1 ms |
324 KB |
Partially correct |
| 12 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 13 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 14 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 15 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 16 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 17 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 18 |
Partially correct |
1 ms |
324 KB |
Partially correct |
| 19 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 20 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 21 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 22 |
Partially correct |
1 ms |
320 KB |
Partially correct |
| 23 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 24 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 25 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 26 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 27 |
Partially correct |
1 ms |
316 KB |
Partially correct |
| 28 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 29 |
Partially correct |
1 ms |
324 KB |
Partially correct |
| 30 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 2 |
Partially correct |
0 ms |
212 KB |
Partially correct |
| 3 |
Partially correct |
0 ms |
212 KB |
Partially correct |
| 4 |
Partially correct |
0 ms |
212 KB |
Partially correct |
| 5 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 6 |
Partially correct |
0 ms |
212 KB |
Partially correct |
| 7 |
Partially correct |
1 ms |
320 KB |
Partially correct |
| 8 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 9 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 10 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 11 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 12 |
Partially correct |
0 ms |
212 KB |
Partially correct |
| 13 |
Partially correct |
0 ms |
320 KB |
Partially correct |
| 14 |
Partially correct |
0 ms |
320 KB |
Partially correct |
| 15 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 16 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 17 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 18 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 19 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 20 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 21 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 22 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 23 |
Partially correct |
1 ms |
324 KB |
Partially correct |
| 24 |
Partially correct |
1 ms |
468 KB |
Partially correct |
| 25 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 26 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 27 |
Partially correct |
1 ms |
324 KB |
Partially correct |
| 28 |
Partially correct |
1 ms |
324 KB |
Partially correct |
| 29 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 30 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 31 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 32 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 33 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 34 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 35 |
Partially correct |
1 ms |
324 KB |
Partially correct |
| 36 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 37 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 38 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 39 |
Partially correct |
1 ms |
320 KB |
Partially correct |
| 40 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 41 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 42 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 43 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 44 |
Partially correct |
1 ms |
316 KB |
Partially correct |
| 45 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 46 |
Partially correct |
1 ms |
324 KB |
Partially correct |
| 47 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 48 |
Partially correct |
52 ms |
7472 KB |
Partially correct |
| 49 |
Partially correct |
60 ms |
8236 KB |
Partially correct |
| 50 |
Partially correct |
50 ms |
8176 KB |
Partially correct |
| 51 |
Partially correct |
48 ms |
6432 KB |
Partially correct |
| 52 |
Partially correct |
61 ms |
8140 KB |
Partially correct |
| 53 |
Partially correct |
50 ms |
7372 KB |
Partially correct |
| 54 |
Partially correct |
29 ms |
9796 KB |
Partially correct |
| 55 |
Partially correct |
61 ms |
20172 KB |
Partially correct |
| 56 |
Partially correct |
76 ms |
14076 KB |
Partially correct |
| 57 |
Partially correct |
55 ms |
12104 KB |
Partially correct |
| 58 |
Partially correct |
53 ms |
10268 KB |
Partially correct |
| 59 |
Partially correct |
55 ms |
8380 KB |
Partially correct |
| 60 |
Partially correct |
40 ms |
8512 KB |
Partially correct |
| 61 |
Partially correct |
42 ms |
8724 KB |
Partially correct |
| 62 |
Partially correct |
47 ms |
8672 KB |
Partially correct |
| 63 |
Partially correct |
49 ms |
8168 KB |
Partially correct |
| 64 |
Partially correct |
47 ms |
8492 KB |
Partially correct |
| 65 |
Partially correct |
53 ms |
8652 KB |
Partially correct |
| 66 |
Partially correct |
40 ms |
8172 KB |
Partially correct |
| 67 |
Partially correct |
32 ms |
6536 KB |
Partially correct |
| 68 |
Partially correct |
47 ms |
7384 KB |
Partially correct |
| 69 |
Partially correct |
44 ms |
8676 KB |
Partially correct |
| 70 |
Partially correct |
45 ms |
8140 KB |
Partially correct |
| 71 |
Partially correct |
29 ms |
6164 KB |
Partially correct |
| 72 |
Partially correct |
33 ms |
6852 KB |
Partially correct |
| 73 |
Partially correct |
45 ms |
8632 KB |
Partially correct |
| 74 |
Partially correct |
43 ms |
7920 KB |
Partially correct |
| 75 |
Partially correct |
50 ms |
8012 KB |
Partially correct |
| 76 |
Partially correct |
51 ms |
8128 KB |
Partially correct |
| 77 |
Partially correct |
57 ms |
8188 KB |
Partially correct |
| 78 |
Partially correct |
30 ms |
5588 KB |
Partially correct |
| 79 |
Partially correct |
40 ms |
6476 KB |
Partially correct |
| 80 |
Partially correct |
52 ms |
8044 KB |
Partially correct |
| 81 |
Partially correct |
51 ms |
8384 KB |
Partially correct |
| 82 |
Partially correct |
49 ms |
8416 KB |
Partially correct |
