daily 2

CF 1256E

struct node {
  int a, id;
};
void solve() {
  int n;
  cin >> n;
  vector<node> a(n + 1);
  vector<int> group(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> a[i].a;
    a[i].id = i;
  }
  sort(a.begin() + 1, a.end(), [&](node a, node b) { return a.a < b.a; });
  vector<int> dp(n + 1);
  dp[3] = a[3].a - a[1].a;
  int cur_min = 1e9, cnt = 0;
  for (int i = 4; i <= n; ++i) {
    if (i >= 6 && cur_min > dp[i - 3] - a[i - 2].a) {
      cur_min = dp[i - 3] - a[i - 2].a;  // we generate another team
      cnt = i - 2;  // write down the start of current group
    }
    dp[i] = dp[i - 1] + a[i].a - a[i - 1].a;  // new team
    group[i] = group[i - 1];
    if (dp[i] > cur_min + a[i].a) {
      dp[i] = cur_min + a[i].a;
      group[i] = cnt;
    }
  }
  int ans = 1, cur = group[n];
  vector<int> ans_sets(n + 1);
  for (int i = n; i >= 1; --i) {
    ans_sets[a[i].id] = ans;
    if (i == cur) {
      ans++;
      cur = group[i - 1];
    }
  }
  cout << dp[n] << ' ' << ans << '\n';
  for (int i = 1; i <= n; ++i) {
    cout << ans_sets[i] << " \n"[i == n];
  }
  return;
}

CF 1294F

void solve() {
  int n;
  cin >> n;
  vector<vector<int>> E(n + 1);
  for (int i = 1; i <= n; ++i) {
    int u, v;
    cin >> u >> v;
    E[u].push_back(v);
    E[v].push_back(u);
  }
  int c = 0, st = 0, ed = 0;
  vector<int> dis(n + 1), bef(n + 1);
  // find diameter
  function<void(int)> dfs = [&](int x) {
    c = dis[x] > dis[c] ? x : c;
    for (int v : E[x]) {
      if (v == bef[x]) continue;
      dis[v] = dis[x] + 1;
      bef[v] = x;
      dfs(v);
    }
  };
  dfs(1);
  st = c;
  dis[st] = 0;
  bef[st] = -1;
  dfs(st);
  ed = c;
  queue<pii> q;
  vector<int> vis(n + 1);
  while (c != -1) {
    q.push({c, 0});
    vis[c] = 1;
    c = bef[c];
  }
  int d, x, extra = 0, p = bef[ed];
  while (!q.empty()) {
    x = q.front().first;
    d = q.front().second;
    q.pop();
    if (d > extra) {
      p = x;
      extra = d;
    }
    for (int v : E[x]) {
      if (vis[v]) {
        continue;
      }
      q.push({v, d + 1});
      vis[v] = 1;
    }
  }
  cout << extra + dis[ed] << '\n';
  cout << st << ' ' << ed << ' ' << p << '\n';
  return;
}