Submission #1268339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268339		aeg	Min-max tree (BOI18_minmaxtree)	C++20	100 / 100	231 ms	35116 KiB

minmaxtree

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, pair<int, int>>> minis, maxis;

vector<vector<int>> adj;

vector<int> par;
vector<int> height;
vector<int> maxl, minl;

void dfs(int s, int p) {
  par[s] = p;
  for (auto &x : adj[s])
    if (x != p) {
      height[x] = height[s] + 1;
      dfs(x, s);
    }
}

struct dsu {
  vector<int> par;
  dsu(int n) : par(n) {
    for (int i = 0; i < n; i++)
      par[i] = i;
  }

  int find(int a) {
    if (par[a] == a)
      return a;
    return par[a] = find(par[a]);
  }

  void unify(int a, int b) {
    a = find(a), b = find(b);
    if (a == b)
      return;
    if (height[a] > height[b])
      swap(a, b);
    par[b] = a;
  }
};

struct dinic {
  vector<vector<int>> adj;
  struct flowEdge {
    int v, u;
    bool cap;
    flowEdge(int v, int u, bool cap) : v(v), u(u), cap(cap) {}
  };
  vector<flowEdge> edges;
  int n, m = 0;
  int s, t;
  vector<int> lvl, ptr;

  dinic(int n)
      : n(n), lvl(n, 0), ptr(n, 0), adj(n, vector<int>()), s(0), t(n - 1) {}

  void add_edge(int u, int v) {
    edges.emplace_back(u, v, true);
    edges.emplace_back(v, u, false);
    adj[u].emplace_back(m++);
    adj[v].emplace_back(m++);
  }

  queue<int> q;
  bool bfs() {
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      for (int i : adj[v]) {
        if (!edges[i].cap)
          continue;
        if (lvl[edges[i].u] != -1)
          continue;
        lvl[edges[i].u] = lvl[v] + 1;
        q.push(edges[i].u);
      }
    }
    return lvl[t] != -1;
  }

  bool dfs(int v, bool push) {
    if (!push)
      return 0;
    if (v == t)
      return push;

    for (int &cid = ptr[v]; cid < adj[v].size(); cid++) {
      int id = adj[v][cid];
      int u = edges[id].u;
      if (lvl[v] + 1 != lvl[u])
        continue;
      bool tr = dfs(u, edges[id].cap);
      if (!tr)
        continue;
      edges[id].cap = false;
      edges[id ^ 1].cap = true;
      return tr;
    }
    return false;
  }

  int flow() {
    int f = 0;
    while (true) {
      fill(lvl.begin(), lvl.end(), -1);
      lvl[s] = 0;
      q.push(s);
      if (!bfs())
        break;
      fill(ptr.begin(), ptr.end(), 0);
      while (bool push = dfs(s, true)) {
        f++;
      }
    }
    return f;
  }
};

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n;
  cin >> n;
  adj = vector<vector<int>>(n, vector<int>());
  par = height = vector<int>(n, 0);
  maxl = minl = vector<int>(n, -1);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  dfs(0, -1);

  int k;
  cin >> k;
  map<int, int> dict;
  vector<int> revdict(k);
  for (int i = 0; i < k; i++) {
    char c;
    int x, y, z;
    cin >> c >> x >> y >> z;
    x--;
    y--;
    if (c == 'm')
      minis.emplace_back(z, pair<int, int>{x, y});
    else
      maxis.emplace_back(z, pair<int, int>{x, y});

    dict[z] = i;
    revdict[i] = z;
  }

  sort(maxis.begin(), maxis.end());
  sort(minis.begin(), minis.end(), greater<pair<int, pair<int, int>>>());

  dsu uf(n);

  for (int i = 0; i < maxis.size(); i++) {
    auto [l, r] = maxis[i].second;
    int val = maxis[i].first;
    l = uf.find(l), r = uf.find(r);
    while (l != r) {
      if (height[r] > height[l])
        swap(r, l);
      maxl[l] = val;
      uf.unify(l, par[l]);
      l = uf.find(l), r = uf.find(r);
    }
  }

  dsu uf2(n);

  for (int i = 0; i < minis.size(); i++) {
    auto [l, r] = minis[i].second;
    int val = minis[i].first;
    l = uf2.find(l), r = uf2.find(r);
    while (l != r) {
      if (height[r] > height[l])
        swap(r, l);
      minl[l] = val;
      uf2.unify(l, par[l]);
      l = uf2.find(l), r = uf2.find(r);
    }
  }

  // copy(minl.begin(), minl.end(), ostream_iterator<int>(cout, " "));
  // cout << '\n';
  // copy(maxl.begin(), maxl.end(), ostream_iterator<int>(cout, " "));
  // cout << '\n';

  // 0 = source
  // 1 -- n - 1 = edges
  // n -- n + k - 1 = values
  // n + k = target
  dinic flow(n + k + 1);
  for (int i = 1; i < n; i++)
    flow.add_edge(0, i);
  for (int i = 1; i < n; i++) {
    if (minl[i] != -1)
      flow.add_edge(i, n + dict[minl[i]]);
    if (maxl[i] != -1)
      flow.add_edge(i, n + dict[maxl[i]]);
  }
  for (int i = n; i < n + k; i++)
    flow.add_edge(i, n + k);

  int debug = flow.flow();
  if (debug != k)
    return -1;
  vector<int> ans(n, -1);
  for (int i = 0; i < flow.edges.size(); i++) {
    if (flow.edges[i].cap == false && flow.edges[i].v < n &&
        flow.edges[i].u >= n)
      ans[flow.edges[i].v] = revdict[flow.edges[i].u - n];
  }
  for (int i = 1; i < n; i++)
    if (ans[i] == -1) {
      if (minl[i] == -1)
        ans[i] = 0;
      else
        ans[i] = minl[i];
    }

  for (int i = 1; i < n; i++) {
    cout << i + 1 << ' ' << par[i] + 1 << ' ' << ans[i] << '\n';
  }
}

• Subtask 1: 7 / 7
• Subtask 2: 22 / 22
• Subtask 3: 29 / 29
• Subtask 4: 42 / 42