Submission #272945

#	Time	Username	Problem	Language	Result	Execution time	Memory
272945		ipaljak	Roller Coaster Railroad (IOI16_railroad)	C++14	34 / 100	2088 ms	55432 KiB

railroad

#include "railroad.h"

#include <bits/stdc++.h>

using namespace std;

#define TRACE(x) cerr << #x << " " << x << endl
#define _ << " " <<

using llint = long long;

int n, m;
llint sol;

vector<int> v;
map<int, int> deg, dad, open;

int find(int x) {
  if (dad[x] == x) return x;
  return dad[x] = find(dad[x]);
}

void unite(int x, int y) {
  if (rand() % 2)
    dad[find(x)] = find(y);
  else
    dad[find(y)] = find(x);
}

llint plan_roller_coaster(vector<int> s, vector<int> t) {
  srand(time(NULL));
  m = (int)s.size();
  for (int i = 0; i < m; ++i) {
    v.emplace_back(s[i]);
    v.emplace_back(t[i]);
  }

  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());

  n = (int)v.size();
  for (int node : v) dad[node] = node;

  s.emplace_back(v[n - 1]);
  t.emplace_back(v[0]);
  ++m;

  for (int i = 0; i < m; ++i) {
    deg[s[i]]++; deg[t[i]]--;
    unite(s[i], t[i]);
  }

  vector<pair<int, int>> e;
  for (int i = 0; i < n - 1; ++i) {
    if (i != 0) open[v[i]] = open[v[i - 1]];
    open[v[i]] += deg[v[i]];
    if (open[v[i]] == 0) {
      e.emplace_back(v[i], v[i + 1]);
      continue;
    }
    unite(v[i], v[i + 1]);
    if (open[v[i]] > 0)
      sol += (llint) open[v[i]] * (v[i + 1] - v[i]);
  }

  sort(e.begin(), e.end(),
       [](const pair<int, int> &A, const pair<int, int> &B) {
         return A.second - A.first < B.second - B.first;
       });

  for (const auto &p : e) {
    if (find(p.first) == find(p.second)) continue;
    sol += (llint) p.second - p.first;
    unite(p.first, p.second);
  }

  return sol;
}

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