Submission #1130926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130926		yellowtoad	Roller Coaster Railroad (IOI16_railroad)	C++20	100 / 100	438 ms	43592 KiB

railroad

#include "railroad.h"
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

long long d[400010], ans, cnt, p[400010];
vector<int> discrete;
vector<pair<long long,pair<int,int>>> edge;
map<int,int> mp;

int dsu(int u) {
    if (p[u] == u) return u;
    return p[u] = dsu(p[u]);
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    s.push_back(1e9); t.push_back(1);
    int n = (int) s.size();
    for (int i = 0; i < n; i++) {
        discrete.push_back(s[i]);
        discrete.push_back(t[i]);
    }
    sort(discrete.begin(),discrete.end());
    for (int i = 0; i < discrete.size(); i++) mp[discrete[i]] = i;
    for (int i = 0; i < n; i++) {
        int u = mp[s[i]], v = mp[t[i]];
        d[u]--;
        d[v]++;
        edge.push_back({0,{u,v}});
    }
    for (int i = 0; i < (int)discrete.size()-1; i++) {
        cnt += d[i];
        if (cnt < 0) ans += (-cnt)*(discrete[i+1]-discrete[i]);
        if (cnt) edge.push_back({0,{i,i+1}});
        else edge.push_back({discrete[i+1]-discrete[i],{i,i+1}});
    }
    sort(edge.begin(),edge.end());
    for (int i = 0; i < discrete.size(); i++) p[i] = i;
    for (int i = 0; i < edge.size(); i++) {
        long long w = edge[i].first, u = edge[i].second.first, v = edge[i].second.second;
        if (dsu(u) != dsu(v)) {
            p[dsu(u)] = p[dsu(v)];
            ans += w;
        }
    }
    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