제출 #849827

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
849827		ogkostya	Closing Time (IOI23_closing)	C++17	8 / 100	106 ms	31164 KiB

closing

#include "closing.h"

#include <vector>
#include <utility>
#include <map>

std::vector<std::pair<int, int>> down[200020];

std::vector<std::pair<long long, int>> build(int N, int X)
{
    std::multimap<long long, int> map = {};
    std::vector<bool> f(N);
    std::vector<std::pair<long long, int>> ans = {};

    f[X] = true;
    map.insert(std::make_pair(0LL, X));
    long long sum = 0;
    while (map.size() > 0)
    {
        std::multimap<long long, int>::iterator it = map.lower_bound(-1);
        long long w = it->first;
        int ii = it->second;
        map.erase(it);

        sum += w;
        ans.push_back(std::make_pair(sum, 1 + ans.size()));

        for (size_t i = 0; i < down[ii].size(); i++)
        {
            if (!f[down[ii][i].first])
            {
                f[down[ii][i].first] = true;
                map.insert(std::make_pair(w + down[ii][i].second, down[ii][i].first));
            }
        }
    }
    return ans;
}


int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    for (int i = 0; i < N; i++)
    {
        down[i].clear();
    }

    for (size_t i = 0; i < W.size(); i++)
    {
        int a = U[i];
        int b = V[i];

        down[a].push_back(std::make_pair(b, W[i]));
        down[b].push_back(std::make_pair(a, W[i]));
    }

    std::vector<std::pair<long long, int>> dx = build(N, X);
    std::vector<std::pair<long long, int>> dy = build(N, Y);

    int ans = 0;
    for (size_t i = 0; i < dy.size(); i++)
    {
        if (dy[i].first > K)
            break;
        ans = std::max(ans, dy[i].second);
    }
    int iy = dy.size() - 1;
    for (size_t i = 0; i < dx.size(); i++)
    {
        if (dx[i].first > K)
            break;
        while (iy >= 0 && dx[i].first + dy[iy].first > K)
        {
            iy--;
        }
        if (iy >= 0)
            ans = std::max(ans, dx[i].second + dy[iy].second);
        else
            ans = std::max(ans, dx[i].second);
    }
    
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17