Submission #1191692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191692		LucaLucaM	Roller Coaster Railroad (IOI16_railroad)	C++20	100 / 100	108 ms	21404 KiB

railroad

#include "railroad.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

#define debug(x) #x << " = " << x << '\n'

using ll = long long;

const int INF = 1e9;

namespace DSU {
  std::vector<int> p;
  std::vector<int> sz;
  void init(int n) {
    p.resize(n + 1);
    sz.resize(n + 1, 1);
    for (int i = 0; i <= n; i++) {
      p[i] = i;
    }
  }
  int root(int u) {
    return p[u] == u? u : p[u] = root(p[u]);
  }
  void join(int u, int v) {
    u = root(u); 
    v = root(v);
    if (u != v) {
      p[u] = v;
      sz[v] += sz[u];
    }
  }
  bool isConnected() {
    return sz[root(1)] == (int) p.size() - 1;
  }
};

struct Event {
  int when, type, index;
  bool operator < (const Event &other) const {
    if (when != other.when) {
      return when < other.when;
    }
    return type < other.type;
  }
};

struct Edge {
  int c, u, v;
  bool operator < (const Edge &other) const {
    return c < other.c;
  }
};

ll plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
  int n = (int) s.size();
  s.push_back(INF);
  t.push_back(1);
  DSU::init(n + 1);

  std::vector<Event> events;
  for (int i = 0; i <= n; i++) {
    events.push_back({s[i], +1, i});
    events.push_back({t[i], -1, i});
  }
  std::sort(events.begin(), events.end());
  
  int delta = 0;
  ll answer = 0;

  std::vector<Edge> edges;

  for (int i = 0; i + 1 < (int) events.size(); i++) {
    delta += events[i].type;
    answer += (ll) std::max(0, delta) * (events[i + 1].when - events[i].when);
    edges.push_back({events[i + 1].when - events[i].when, events[i].index, events[i + 1].index});
    if (delta != 0 || events[i].when == events[i + 1].when) {
      DSU::join(events[i].index, events[i + 1].index);
    }
  }
  
  std::sort(edges.begin(), edges.end());

  for (const auto &[cost, i, j] : edges) {
    if (DSU::root(i) != DSU::root(j)) {
      answer += cost;
      DSU::join(i, j);
    }
  }

  return answer;
}

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: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 30 / 30
• Subtask 4: 36 / 36