oj.uz

Submission #1050893

# Submission time Handle Problem Language Result Execution time Memory
1050893 2024-08-09T16:23:22 Z duckindog Village (BOI20_village) C++17
0 / 100
 2 ms 9292 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
const long long MAX = 1'000'000'000'000'000'000;
int n;
vector<int> ad[N];

namespace findMin { 
  long long f[N][2];
  vector<tuple<int, int, int>> trace[N][2];
  void dfs0(int u, int p = -1) { 
    f[u][1] = 0;
    
    vector<int> vt;
    for (const auto& v : ad[u]) { 
      if (v == p) continue;
      dfs0(v, u);
      vt.push_back(v);
    }

    if (vt.size()) { 
      sort(vt.begin(), vt.end(), [&](const auto& a, const auto& b) { 
        return f[a][1] - f[a][0] > f[b][1] - f[b][0];
      });

      auto transition = [&](long long& ret, auto& trace, vector<int> vt) { 
        while (vt.size() > 1) { 
          int value = f[vt.back()][1] + f[vt.end()[-2]][1] + 4;  
          if (value <= f[vt.back()][0] + f[vt.end()[-2]][0]) { 
            ret = min(MAX, ret + value);
            trace.emplace_back(0, vt.back(), vt.end()[-2]);
            vt.pop_back();
            vt.pop_back();
          } else break;
        }
        for (const auto& x : vt) {
          ret = min(MAX, ret + f[x][0]);
          trace.emplace_back(1, x, 0);
        }
      };

      transition(f[u][1], trace[u][1], vt);

      f[u][0] = f[vt.back()][1] + 2;
      trace[u][0].emplace_back(2, vt.back(), 1);
      transition(f[u][0], trace[u][0], vector<int>(vt.begin(), vt.end() - 1));

      if (f[u][0] > f[u][1] + 2) { 
        f[u][0] = f[u][1] + 2;
        trace[u][0] = {make_tuple(3, vt.back(), 0)};
      } 
    }

    if (f[u][1] >= MAX) f[u][1] = 2 * MAX;
    if (f[u][0] >= MAX) f[u][0] = MAX;
  }

  int vt[N];
  void dfs1(int u, int st) { 
    for (const auto& [type, a, b] : trace[u][st]) { 
      if (!type) { 
        dfs1(a, 1); dfs1(b, 1);
        swap(vt[a], vt[b]);
      } else if (type == 1) {
        dfs1(a, 0);
      } else if (type == 2) { 
        dfs1(a, 1);
        swap(vt[u], vt[a]);
      } else { 
        dfs1(u, 1);
        swap(vt[u], vt[a]);
      }
    }
  }
  int length;
  vector<int> answer;
  void solve() { 
    memset(f, 14, sizeof f);
    dfs0(1);
    iota(vt + 1, vt + n + 1, 1);
    dfs1(1, 0);
    length = f[1][0];
    answer = vector<int>(vt + 1, vt + n + 1);
  }
}

namespace findMax { 
  int length;
  vector<int> answer;
  void solve() { 
    length = 1;
    answer = vector<int>(n, 1);
  }
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for (int i = 1; i < n; ++i) { 
    int u, v; cin >> u >> v;
    ad[u].push_back(v);
    ad[v].push_back(u);
  }

  findMin::solve();
  findMax::solve();

  cout << findMin::length << " " << findMax::length << "\n";
  for (int i = 0; i < n; ++i) cout << findMin::answer[i] << " \n"[i == n - 1];
  for (int i = 0; i < n; ++i) cout << findMax::answer[i] << " \n"[i == n - 1];
}

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 9048 KB Partially correct
2 Partially correct 1 ms 9052 KB Partially correct
3 Partially correct 1 ms 9292 KB Partially correct
4 Partially correct 2 ms 9052 KB Partially correct
5 Partially correct 1 ms 9052 KB Partially correct
6 Incorrect 1 ms 9052 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 9052 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 1 ms 9048 KB Partially correct
2 Partially correct 1 ms 9052 KB Partially correct
3 Partially correct 1 ms 9292 KB Partially correct
4 Partially correct 2 ms 9052 KB Partially correct
5 Partially correct 1 ms 9052 KB Partially correct
6 Incorrect 1 ms 9052 KB Output isn't correct
7 Halted 0 ms 0 KB -