Submission #94571

#	Time	Username	Problem	Language	Result	Execution time	Memory
94571		wxh010910	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	439 ms	15208 KiB

railroad

#include <bits/stdc++.h>
#include "railroad.h"

using namespace std;

class dsu {
 public:
  vector<int> p;
  int n;

  dsu(int n): n(n) {
    p.resize(n);
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
  }

  inline int find(int x) {
    while (x != p[x]) {
      x = p[x] = p[p[x]];
    }
    return x;
  }

  inline bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return false;
    } else {
      p[x] = y;
      return true;
    }
  }
};

long long plan_roller_coaster(vector<int> s, vector<int> t) {
  int n = s.size();
  vector<int> disc;
  for (int i = 0; i < n; ++i) {
    disc.push_back(s[i]);
    disc.push_back(t[i]);
  }
  sort(disc.begin(), disc.end());
  disc.erase(unique(disc.begin(), disc.end()), disc.end());
  int m = disc.size();
  dsu d(m);
  vector<int> pass_by(m);
  for (int i = 0; i < n; ++i) {
    s[i] = lower_bound(disc.begin(), disc.end(), s[i]) - disc.begin();
    t[i] = lower_bound(disc.begin(), disc.end(), t[i]) - disc.begin();
    ++pass_by[s[i]];
    --pass_by[t[i]];
    d.unite(s[i], t[i]);
  }
  long long ans = 0;
  vector<pair<int, int>> edges;
  for (int i = 0; i < m - 1; ++i) {
    pass_by[i + 1] += pass_by[i];
    if (pass_by[i] > 1) {
      ans += (long long) (disc[i + 1] - disc[i]) * (pass_by[i] - 1);
    }
    if (pass_by[i] == 1) {
      edges.emplace_back(disc[i + 1] - disc[i], i);
    } else {
      d.unite(i, i + 1);
    }
  }
  sort(edges.begin(), edges.end());
  for (auto p : edges) {
    if (d.unite(p.second, p.second + 1)) {
      ans += p.first;
    }
  }
  return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 30 / 30
• Subtask 4: 36 / 36