oj.uz

Submission #854594

# Submission time Handle Problem Language Result Execution time Memory
854594 2023-09-28T06:32:21 Z gun_gan Village (BOI20_village) C++17
0 / 100
 4 ms 15936 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MX = 5e5 + 5;
 
int N;
vector<int> g[MX];

int r, sz[MX], pp[MX], minCost = 0;

void dfs(int v, int p) {
      for(auto u : g[v]) {
            if(u == p) continue;
            dfs(u, v);
            sz[v] += sz[u];
      }
      sz[v]++;

      int lst = 0;
      for(auto u : g[v]) {
            if(u == p) continue;
            if(sz[u] & 1) {
                  if(lst) {
                        minCost += 4;
                        swap(pp[u], pp[lst]);
                        lst = 0;
                  } else {
                        lst = u;
                  }
            }
      }

      if(lst) {
            minCost += 2;
            swap(pp[lst], pp[v]);
      }
}

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      cin >> N;
      for(int i = 1; i <= N; i++) pp[i] = i;
      for(int i = 0; i < N - 1; i++) {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
      }

      r = 0;
      for(int i = 1; i <= N; i++) {
            if(g[i].size() > g[r].size()) r = i;
      }

      dfs(r, 0);

      if(pp[r] == r) {
            assert(N & 1);
            for(int u : g[r]) {
                  if(sz[u] & 1) {
                        swap(pp[r], pp[u]);
                        break;
                  }
            }

            if(pp[r] == r) {
                  minCost += 2;
                  swap(pp[r], pp[g[r][0]]);
            }
      }

      for(int i = 1; i <= N; i++) assert(pp[i] != i);

      cout << minCost << " " << 1 << '\n';
      for(int i = 1; i <= N; i++) cout << pp[i] << " ";
      cout << '\n';
      for(int i = 1; i <= N; i++) cout << 1 << " ";
      cout << '\n';
}

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 15708 KB Partially correct
2 Partially correct 3 ms 15708 KB Partially correct
3 Partially correct 3 ms 15708 KB Partially correct
4 Partially correct 4 ms 15708 KB Partially correct
5 Partially correct 3 ms 15928 KB Partially correct
6 Partially correct 4 ms 15708 KB Partially correct
7 Partially correct 4 ms 15708 KB Partially correct
8 Partially correct 3 ms 15708 KB Partially correct
9 Partially correct 3 ms 15936 KB Partially correct
10 Partially correct 4 ms 15712 KB Partially correct
11 Partially correct 3 ms 15704 KB Partially correct
12 Partially correct 3 ms 15708 KB Partially correct
13 Incorrect 3 ms 15708 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 15708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 15708 KB Partially correct
2 Partially correct 3 ms 15708 KB Partially correct
3 Partially correct 3 ms 15708 KB Partially correct
4 Partially correct 4 ms 15708 KB Partially correct
5 Partially correct 3 ms 15928 KB Partially correct
6 Partially correct 4 ms 15708 KB Partially correct
7 Partially correct 4 ms 15708 KB Partially correct
8 Partially correct 3 ms 15708 KB Partially correct
9 Partially correct 3 ms 15936 KB Partially correct
10 Partially correct 4 ms 15712 KB Partially correct
11 Partially correct 3 ms 15704 KB Partially correct
12 Partially correct 3 ms 15708 KB Partially correct
13 Incorrect 3 ms 15708 KB Output isn't correct
14 Halted 0 ms 0 KB -