Submission #600349

#	Time	Username	Problem	Language	Result	Execution time	Memory
600349		MilosMilutinovic	Roller Coaster Railroad (IOI16_railroad)	C++14	100 / 100	129 ms	18276 KiB

railroad

/**
 *    author:  wxhtzdy
 *    created: 20.07.2022 18:41:11
**/
#include <bits/stdc++.h>

using namespace std;

class dsu {
  public:
  vector<int> p;
  int n;
  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }
  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }
  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};

long long plan_roller_coaster(vector<int> s, vector<int> t) {
  int n = (int) s.size();      
  vector<tuple<int, int, int>> ev;
  for (int i = 0; i < n; i++) {
    ev.emplace_back(s[i], +1, i);
    ev.emplace_back(t[i], -1, i);
  }
  ev.emplace_back(1e9, +1, n);
  ev.emplace_back(1, -1, n);
  dsu d(n + 1);
  sort(ev.begin(), ev.end());
  int bal = 0;              
  long long ans = 0;
  vector<tuple<int, int, int>> edges;
  for (int i = 0; i < (int) ev.size() - 1; i++) {
    int len = get<0>(ev[i + 1]) - get<0>(ev[i]);
    bal += get<1>(ev[i]);
    if (bal > 0) {
      ans += bal * 1LL * len;
    } 
    if (bal == 0) {
      edges.emplace_back(len, get<2>(ev[i]), get<2>(ev[i + 1]));
    } else {
      d.unite(get<2>(ev[i]), get<2>(ev[i + 1]));
    }
  }
  sort(edges.begin(), edges.end());
  for (auto& p : edges) {
    if (d.unite(get<1>(p), get<2>(p))) {
      ans += get<0>(p);
    }
  }
  return ans;
} 

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