제출 #1167248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167248		sheercold	Village (BOI20_village)	C++20	50 / 100	65 ms	29888 KiB

Village

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  int n;
  cin >> n;
  vector<vector<int>> tree(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    tree[u].push_back(v);
    tree[v].push_back(u);
  }
  vector<int> order;
  vector<int> tin(n);
  vector<array<int, 2>> dp(n, array<int, 2>{});
  vector<int> siz(n);
  vector<int> upto(n);
  vector<int> vis(n);
  auto dfs = [&](auto&& self, int v) -> void {
    tin[v] = order.size();
    order.push_back(v);
    vis[v] = 1;
    vector<int> del;
    vector<int> kids;
    siz[v] = 1;
    for (int nxt : tree[v]) {
      if (vis[nxt]) {
        continue;
      }
      self(self, nxt);
      kids.push_back(nxt);
      del.push_back(dp[nxt][1] - dp[nxt][0]);
      dp[v][1] += max(dp[nxt][0], dp[nxt][1]);
      dp[v][0] += dp[nxt][0];
      siz[v] += siz[nxt];
    }
    tree[v] = kids;
    if (!del.empty()) {
      sort(tree[v].begin(), tree[v].end(), [&](auto lhs, auto rhs) -> bool {
        return dp[lhs][1] - dp[lhs][0] > dp[rhs][1] - dp[rhs][0];
      });
      sort(del.begin(), del.end(), greater<>());
      int ind = 0;
      while (ind < del.size() && del[ind] >= 0) {
        dp[v][0] += del[ind];
        ++ind;
      }
      if (ind == 0) {
        dp[v][0] += del[ind];
        ++ind;
      }
      upto[v] = ind;
      dp[v][0] += 2;
    } else {
      dp[v][0] = -1;
    }
  };
  dfs(dfs, 0);
  vector<int> good(n);
  auto dfs2 = [&](auto&& self, int v, int want = 0) -> void {
    if (want == 0) {
      good[v] = 1;
    }
    if (want == 0) {
      for (int i = 0; i < upto[v]; i++) {
        int nxt = tree[v][i];
        self(self, nxt, 1);
      }
      for (int i = upto[v]; i < tree[v].size(); i++) {
        int nxt = tree[v][i];
        self(self, nxt, 0);
      }
    } else {
      for (int i = 0; i < tree[v].size(); i++) {
        int nxt = tree[v][i];
        if (dp[nxt][0] > dp[nxt][1]) {
          self(self, nxt, 0);
        } else {
          self(self, nxt, 1);
        }
      }
    }
  };
  fill(vis.begin(), vis.end(), 0);
  dfs2(dfs2, 0);
  vector<int> ans(n);
  for (int i = 0; i < n; i++) {
    if (!good[i] || vis[i]) {
      continue;
    }
    vector<int> comp;
    queue<int> q;
    vis[i] = 1;
    q.push(i);
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      comp.push_back(v);
      for (int nxt : tree[v]) {
        if (!good[nxt]) {
          vis[nxt] = 1;
          q.push(nxt);
        }
      }
    }
    assert(comp.size() >= 2);
    sort(comp.begin(), comp.end(), [&](auto lhs, auto rhs) -> bool {
      return tin[lhs] < tin[rhs];
    });
    int siz = comp.size();
    for (int i = 0; i < siz; i++) {
      ans[comp[i]] = comp[(i + 1) % siz];
    }
  }
  i64 big = 0;
  for (int i = 0; i < n; i++) {
    big += min(n - siz[i], siz[i]);
  }
  big *= 2;
  cout << 2 * n - dp[0][0] << ' ' << big << '\n';
  for (int i = 0; i < n; i++) {
    cout << ans[i] + 1 << ' ';
  }
  cout << '\n';
  for (int i = 0; i < n; i++) {
    cout << 1 << ' ';
  }
  cout << '\n';
  return 0;
}

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50