Submission #785918

#	Time	Username	Problem	Language	Result	Execution time	Memory
785918		GusterGoose27	Roller Coaster Railroad (IOI16_railroad)	C++17	30 / 100	670 ms	69120 KiB

railroad

#include "railroad.h"

#include <bits/stdc++.h>

using namespace std;

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

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

int n, m = 0;

void dfs(int cur) {
    vis[cur] = 1;
    visits.back().push_back(anticonv[cur]);
    ranges.back().first = min(ranges.back().first, anticonv[cur]);
    ranges.back().second = max(ranges.back().second, anticonv[cur]);
    for (int nxt: edges[cur]) {
        if (!vis[nxt]) dfs(nxt);
    }
}

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(conv[t[i]]);
    sort(events.begin(), events.end()); // 0 start, 1 end
    int sum = 0;
    for (int i = 0; i < events.size()-1; i++) {
        sum += events[i].second ? -1 : 1;
        if (sum < 0) return 1;
        // cerr << conv[events[i].first] << ' ' << sum << '\n';
        if (sum) edges[conv[events[i].first]].push_back(conv[events[i+1].first]);
    }
    assert(conv[1] == 0);
    vector<pii> groups;
    for (int i = 0; i < m; i++) {
        if (vis[i]) continue;
        if (i) return 1;
        vector<int> v; visits.push_back(v);
        ranges.push_back(pii(anticonv[i], anticonv[i]));
        dfs(i);
        groups.push_back(pii(ranges.back().second-ranges.back().first, ranges.size()-1));
    }
    return 0;
    sort(groups.rbegin(), groups.rend());
    set<int> active;
    ll ans = 0;
    for (pii p: groups) {
        int cur = p.second;
        if (cur) {
            auto it = active.upper_bound(ranges[cur].second);
            assert(it != active.end());
            assert(it != active.begin());
            int d = (*it)-ranges[cur].second;
            --it;
            d = min(d, ranges[cur].first-(*it));
            ans += d;
        }
        for (int v: visits[cur]) active.insert(v);
    }
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'll plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:56: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]
   56 |     for (int i = 0; i < events.size()-1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~~

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