Submission #1217176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217176		abczz	Roller Coaster Railroad (IOI16_railroad)	C++20	30 / 100	103 ms	28592 KiB

railroad

#include "railroad.h"
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long

using namespace std;

vector <array<ll, 2>> A, B;
bool visited[200001];
ll nx[200001], G[200001], P[200001], f;
ll dsu(ll u) {
  if (u == P[u]) return u;
  else return P[u] = dsu(P[u]);
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
  A.clear();
  B.clear();
  ll n = s.size()+1;
  f = 0;
  s.push_back((ll)1e9);
  t.push_back(1);
  for (int i=0; i<n; ++i) {
    P[i] = i;
    visited[i] = 0;
    A.push_back({s[i], i});
    B.push_back({t[i], i});
  }
  sort(A.begin(), A.end());
  sort(B.begin(), B.end());
  for (int i=0; i<n; ++i) {
    f += max(0LL, B[i][0]-A[i][0]);
    nx[B[i][1]] = A[i][1];
  }
  ll k = 0;
  for (int i=0; i<n; ++i) {
    if (visited[i]) continue;
    ll u = i;
    while (true) {
      visited[u] = 1, G[u] = k;
      u = nx[u];
      if (u == i) break;
    }
    ++k;
  }
  vector <array<ll, 3>> X;
  vector <array<ll, 3>> W;
  ll x = -1e18, l = 1e18;
  for (int i=0; i<n; ++i) {
    if (x == -1e18) {
      x = max(A[i][0], B[i][0]), l = min(A[i][0], B[i][0]);
    }
    else if (x >= min(A[i][0], B[i][0])) {
      x = max(A[i][0], B[i][0]);
      if (i) {
        ll a = dsu(G[A[i-1][1]]), b = dsu(G[A[i][1]]);
        if (a != b) P[a] = b;
      }
    }
    else {
      X.push_back({l, max(A[i-1][0], B[i-1][0]), G[A[i-1][1]]});
      x = max(A[i][0], B[i][0]), l = min(A[i][0], B[i][0]);
    }
  }
  for (int i=0; i+1<X.size(); ++i) {
    W.push_back({X[i+1][0]-X[i][1], X[i][2], X[i+1][2]});
  }
  sort(W.begin(), W.end());
  for (auto [w, u, v] : W) {
    u = dsu(u), v = dsu(v);
    if (u != v) {
      f += w;
      P[u] = v;
    }
  }
  return f;
}

Compilation message (stderr)

railroad.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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