Submission #939351

#	Time	Username	Problem	Language	Result	Execution time	Memory
939351		boris_mihov	Treatment Project (JOI20_treatment)	C++17	35 / 100	919 ms	524288 KiB

treatment

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 100000 + 10;
const llong INF = 1e18;

int n, m;
struct Interval
{
    int t, l, r, c;
    friend bool operator < (const Interval &a, const Interval &b)
    {
        return a.r < b.r;
    }
};

bool vis[MAXN];
Interval a[MAXN];
llong dist[MAXN];
std::vector <std::pair <int,int>> g[MAXN];
std::priority_queue <std::pair <llong,int>> pq;

void solve()
{
    // std::sort(a + 1, a + 1 + n);
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= n ; ++j)
        {
            if (i != j && a[i].r - a[j].l + 1 >= abs(a[i].t - a[j].t))
            {
                g[i].push_back({j, a[j].c});
            }
        }
    }

    llong ans = INF;
    for (int i = 1 ; i <= n ; ++i)
    {
        dist[i] = INF;
        if (a[i].l == 1)
        {
            dist[i] = a[i].c;
            pq.push({-dist[i], i});
        }
    }

    while (pq.size())
    {
        auto [currDist, node] = pq.top();
        pq.pop();

        if (a[node].r == m)
        {
            ans = dist[node];
            break;
        }

        if (vis[node])
        {
            continue;
        }

        vis[node] = true;
        for (const auto &[u, w] : g[node])
        {
            if (dist[u] > dist[node] + w)
            {
                dist[u] = dist[node] + w;
                pq.push({-dist[u], u});
            }
        }
    }

    if (ans == INF) std::cout << -1 << '\n';
    else std::cout << ans << '\n';
}

void input()
{
    std::cin >> m >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i].t >> a[i].l >> a[i].r >> a[i].c;
    }   
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 61