Submission #409667

#	Time	Username	Problem	Language	Result	Execution time	Memory
409667		DBPhoenix	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	2037 ms	121788 KiB

railroad

#include <bits/stdc++.h>

using namespace std;

#include "railroad.h"

struct Vertex {
    vector<pair<long long, int>> connections;
};

map<int, Vertex> vertices;
map<int, bool> visited;

long long MST(int s)
{
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push(make_pair(0, s));

    long long distance = 0;
    while (!pq.empty())
    {
        pair<long long, int> top = pq.top(); pq.pop();

        if (visited[top.second]) continue;
        else visited[top.second] = true;

        distance += top.first;

        for (pair<long long, int> connection : vertices[top.second].connections) {
            pq.push(make_pair(connection.first, connection.second));
        }
    }

    return distance;
}

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();

    map<int, int> interest;
    interest[1]--;

    for (int i = 0; i < n; i++)
    {
        interest[s[i]]++;
        interest[t[i]]--;

        vertices[s[i]].connections.push_back(make_pair(0, t[i]));
        vertices[t[i]].connections.push_back(make_pair(0, s[i]));
    }

    auto itr = interest.begin();

    long long value = (*itr).second;
    long long balance = max((long long) 0, value);

    auto prev = itr++;

    for (; itr != interest.end(); itr++)
    {
        value += (*itr).second;
        balance += max((long long) 0, value);

        long long _weight = (*itr).first - (*prev).first;
        if (value < 0) _weight = 0;

        vertices[(*prev).first].connections.push_back(make_pair(_weight, (*itr).first));
        vertices[(*itr).first].connections.push_back(make_pair(_weight, (*prev).first));

        prev = itr;
    }

    for (pair<int, int> p : interest)
    {
        value += p.second;
        balance += max((long long) 0, value);
    }

    balance += MST(s[0]);

    return balance;
}

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