Submission #785950

#	Time	Username	Problem	Language	Result	Execution time	Memory
785950		GusterGoose27	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	902 ms	56708 KiB

railroad

#include "railroad.h"

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, int> pli;

const int MAXN = 2e5+5;
const int MAXM = 1e9+5;
const ll inf = (ll)MAXN*MAXM;
vector<pii> edges[2*MAXN];
map<int, int> conv;
int anticonv[2*MAXN];
// ll dist[2*MAXN];
bool vis[2*MAXN];

int n, m = 0;

void ins(int v) {
    if (conv.find(v) != conv.end()) return;
    conv[v] = m;
    anticonv[m++] = v;
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    ins(1);
    ins(MAXM);
    vector<pii> events;
    events.push_back(pii(1, 0));
    events.push_back(pii(MAXM, 1));
    for (int v: s) {
        ins(v);
        events.push_back(pii(v, 1));
    }
    for (int v: t) {
        ins(v);
        events.push_back(pii(v, 0));
    }
    n = s.size();
    for (int i = 0; i < n; i++) edges[conv[s[i]]].push_back(pii(conv[t[i]], 0));
    sort(events.begin(), events.end()); // 0 start, 1 end
    int sum = 0;
    ll ans = 0;
    for (int i = 0; i < events.size()-1; i++) {
        sum += events[i].second ? -1 : 1;
        if (sum < 0) {
            edges[conv[events[i+1].first]].push_back(pii(conv[events[i].first], 0));
            ans += ((ll)events[i+1].first-events[i].first)*(-sum);
        }
        else if (sum > 0) edges[conv[events[i].first]].push_back(pii(conv[events[i+1].first], 0));
        else {
            edges[conv[events[i].first]].push_back(pii(conv[events[i+1].first], events[i+1].first-events[i].first));
            edges[conv[events[i+1].first]].push_back(pii(conv[events[i].first], events[i+1].first-events[i].first));
        }
    }
    priority_queue<pii, vector<pii>, greater<pii>> out;
    out.push(pii(0, 0));
    while (!out.empty()) {
        pii tp = out.top();
        out.pop();
        if (vis[tp.second]) continue;
        vis[tp.second] = 1;
        ans += tp.first;
        int cur = tp.second;
        for (pii p: edges[cur]) {
            if (vis[p.first]) continue;
            out.push(pii(p.second, p.first));
        }
    }
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'll plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0; i < events.size()-1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~~

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