Submission #854605

#	Time	Username	Problem	Language	Result	Execution time	Memory
854605		gun_gan	Village (BOI20_village)	C++17	50 / 100	47 ms	28572 KiB

Village

#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, z = 0;
      for(auto u : g[v]) {
            if(u == p) continue;
            if(pp[u] == u) {
                  if(lst) {
                        minCost += 4;
                        z = u;
                        swap(pp[u], pp[lst]);
                        lst = 0;
                  } else {
                        lst = u;
                  }
            }
      }

      if(lst) {
            minCost += 2;
            swap(pp[lst], pp[v]);
      } else if(z != 0) {
            swap(pp[z], 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) {
            swap(pp[r], pp[g[r][0]]);
            minCost += 2;
      }

      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: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50