Submission #1219605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219605		HappyCapybara	Roller Coaster Railroad (IOI16_railroad)	C++20	100 / 100	507 ms	61708 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

vector<int> p;

int find(int a){
    if (a == p[a]) return p[a];
    return p[a] = find(p[a]);
}

ll plan_roller_coaster(vector<int> s, vector<int> t){
    ll res = 0;
    s.push_back(pow(10, 9));
    t.push_back(1);
    int n = s.size();
    set<int> cc;
    for (int i=0; i<n; i++){
        cc.insert(s[i]);
        cc.insert(t[i]);
    }
    int z = cc.size();
    vector<int> v(z);
    map<int,int> m;
    int cur = 0;
    for (int x : cc){
        m[x] = cur;
        v[cur] = x;
        cur++;
    }
    vector<int> imb(z, 0);
    vector<pair<ll,pair<int,int>>> e;
    for (int i=0; i<n; i++){
        s[i] = m[s[i]];
        t[i] = m[t[i]];
        e.push_back({0, {s[i], t[i]}});
        imb[s[i]]++;
        imb[t[i]]--;
    }
    for (int i=0; i<z-1; i++){
        if (i > 0) imb[i] += imb[i-1];
        if (imb[i] > 0){
            res += (ll)imb[i]*(ll)(v[i+1]-v[i]);
            e.push_back({0, {i, i+1}});
        }
        if (imb[i] < 0){
            e.push_back({0, {i, i+1}});
        }
    }
    for (int i=0; i<z-1; i++) e.push_back({v[i+1]-v[i], {i, i+1}});
    p.resize(z);
    for (int i=0; i<z; i++) p[i] = i;
    sort(e.begin(), e.end());
    for (pair<ll,pair<int,int>> x : e){
        int a = find(x.second.first), b = find(x.second.second);
        if (a == b) continue;
        res += x.first;
        p[b] = a;
    }
    return res;
}

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