Submission #656412

#	Time	Username	Problem	Language	Result	Execution time	Memory
656412		cadmiumsky	Village (BOI20_village)	C++14	0 / 100	4 ms	7380 KiB

Village

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()

using namespace std;
const int nmax = 1e5 + 5, inf = nmax * 5;
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
using ll = long long;

int n;

vector<tii> edg;
vector<int> g[nmax];

int sz[nmax];

void dfs(int node, int f) {
  sz[node] = 1;
  for(auto x : g[node]) {
    if(x != f) dfs(x, node), sz[node] += sz[x];
  }
  if(node != f)
    //cerr << sz[node] << ' ' << n - sz[node] << '\n',
    edg.emplace_back(min(sz[node], n - sz[node]), node, f);
}

namespace DSU {
  int dsu[nmax];
  vector<int> g[nmax * 2];
  int cnt;
  void init() {
    cnt = n + 1;
    for(int i = 0; i <= n * 2; i++) dsu[i] = i;
  }
  int f(int x) { return dsu[x] == x? x : f(dsu[x] = f(dsu[dsu[x]])); }
  void unite(int x, int y) {
    //cerr << x << ' ' << y << '\t';
    x = f(x);
    y = f(y);
    //cerr << x << ' ' << y << '\n';
    if(x != y)
      //cerr << cnt << " -> " << x << ' ' << y << '\n';
      g[cnt].push_back(x),
      g[cnt].push_back(y),
      dsu[x] = dsu[y] = cnt,
      cnt++;
  }
  vector<int> preord;
  void dfs(int node = cnt - 1) {
    if(node <= n)
      preord.push_back(node);
    for(auto x : g[node])
      dfs(x);
  }
    
}

int main() {
  cin >> n;
  for(int i = 1, x, y; i < n; i++) {
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(1, 1);
  sort(all(edg));
  ll sum = 0;
  DSU::init();
  for(auto [c, a, b] : edg)
    sum += c * 2,
    DSU::unite(a, b);
  DSU::dfs();
  using namespace DSU;
  vector<int> nv;
  for(int l = 0, r = n - 1, i = 0; i < n; i++) {
    if(i % 2 == 0)
      nv.push_back(preord[l++]);
    else
      nv.push_back(preord[r--]);
  }
  preord = move(nv);
  preord.push_back(preord[0]);
  vector<int> rez(n);
  for(int i = 0; i < n; i++)
    //cerr << preord[i] << ' ',
    rez[preord[i] - 1] = preord[i + 1];
  cout << 420 << ' ' << sum << '\n';
  for(int i = 0; i < n; i++)
    cout << "1 ";
  cout << '\n';
  for(auto x : rez)
    cout << x << ' ';
  cout << '\n';
  
}

Compilation message (stderr)

Village.cpp: In function 'int main()':
Village.cpp:69:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |   for(auto [c, a, b] : edg)
      |            ^

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