Submission #1245520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245520		Boomyday	Roller Coaster Railroad (IOI16_railroad)	C++20	100 / 100	931 ms	71300 KiB

railroad

//
// Created by adavy on 7/22/2025.
//
#include <bits/stdc++.h>
using namespace std;
#include "railroad.h"
using ll = long long;
#define int long long

struct dsu{
    vector<int> par;
    dsu(int n){
        par.resize(n);
        for(int i=0;i<n;++i) par[i] = i;
    }
    int find(int u){
        if (par[u]==u) return u;
        return par[u] = find(par[u]);
    }
    bool unite(int u, int v){
        u = find(u);
        v = find(v);
        if (u==v) return 1;
        par[u] = v;
        return 0;
    }
};

long long plan_roller_coaster(std::vector<signed> s, std::vector<signed> t) {
    ll ans = 0;
    s.push_back(1e9);
    t.push_back(1);
    int q = s.size();
    set<int> valid_inds;
    vector<pair<int, pair<int, int>>> edges;
    for (auto&x:s) valid_inds.insert(x);
    for (auto&x:t) valid_inds.insert(x);
    vector<int> vvalid(valid_inds.begin(), valid_inds.end());
    int n = vvalid.size();
    for(int i=0;i<n-1;++i) edges.push_back({vvalid[i+1]-vvalid[i],{i, i+1}});
    sort(edges.begin(), edges.end());
    dsu d(n);
    map<int, int> vindex;
    for(int i=0;i<vvalid.size();++i) vindex[vvalid[i]] = i;
    vector<int> sums(n,0);
    for(int i=0;i<q;++i){
        sums[vindex[s[i]]]++;
        sums[vindex[t[i]]]--;
        d.unite(vindex[s[i]], vindex[t[i]]);
    }

    vector<int> prefs(n-1); // n-1 gaps covering the n nodes
    prefs[0] = sums[0];
    for(int i=1;i<n-1;++i) prefs[i] = prefs[i-1] + sums[i];
    for(int i=0;i<n-1;++i){
        if (prefs[i] != 0){
            d.unite(i, i+1);
            if (prefs[i] > 0) ans += prefs[i]*(vvalid[i+1] - vvalid[i]);
        }
    }
    for(auto&[c, e]:edges){
        if (d.unite(e.first, e.second) == false) ans += c;
    }

    return ans;
}

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