Submission #1275995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275995		julia_08	Village (BOI20_village)	C++20	0 / 100	2 ms	12088 KiB

Village

#include <bits/stdc++.h>
#define int long long

using namespace std;

using ll = long long;

const int MAXN = 1e5 + 10;

int p[MAXN];

int deg[MAXN], marc[MAXN];

vector<int> adj[MAXN], c[MAXN];

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

  int n; cin >> n;

  for(int i=1; i<n; i++){
    
    int a, b; cin >> a >> b;
    
    adj[a].push_back(b);
    adj[b].push_back(a);
    
    deg[a] ++; deg[b] ++;

  }

  queue<int> q;

  for(int i=1; i<=n; i++){
    if(deg[i] == 1){
      q.push(i);
    }
  }

  int ans = 0;

  while(!q.empty()){

    int v = q.front();
    q.pop();

    if(!c[v].empty()){

      marc[v] = 1;

      int sz = (int) c[v].size();

      ans += 2 * sz;

      if(sz % 2 == 0){

        while(sz > 2){

          auto [a, b] = make_pair(c[v][sz - 2], c[v][sz - 1]);

          p[a] = b;
          p[b] = a;

          sz -= 2;

        }

        auto [a, b] = make_pair(c[v][0], c[v][1]);

        p[v] = a;
        p[b] = v;
        p[a] = b;

      } else{

        while(sz > 1){

          auto [a, b] = make_pair(c[v][sz - 2], c[v][sz - 1]);

          p[a] = b;
          p[b] = a;

          sz -= 2;

        }

        p[v] = c[v][0];
        p[c[v][0]] = v;

      }

    }

    for(auto u : adj[v]){

      deg[u] --;
      if(!marc[v]) c[u].push_back(v);

      if(deg[u] == 1) q.push(u);

    }

  }


  // min:

  cout << ans << "\n";

  for(int i=1; i<=n; i++) cout << p[i] << " ";

  cout << "\n";

  // max: 

  cout << "1\n";

  for(int i=1; i<=n; i++) cout << "1 ";

  cout << "\n";

  return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 38
• Subtask 3: 0 / 50