제출 #849934

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
849934		ogkostya	봉쇄 시간 (IOI23_closing)	C++17	8 / 100	92 ms	28604 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();
    }

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

        if (a == i && b == i + 1 || b == i && a == i + 1)
        {

        }
        else
        {
            lin = false;
        }

        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);
    }

    if (lin)
    {
        long long sx = 0;
        long long sy = 0;

        int x = X;
        int y = Y;
        long long sum = 0;

        std::vector<int> WW(N);
        int count = 2;
        while (x < y - 1)
        {
            if (sx + W[x] < sy + W[y - 1])
            {
                sum += sx + W[x];
                sx += W[x];
                x++;
                WW[x] = sx;
                count++;
            }
            else
            {
                sum += sy + W[y - 1];
                sy += W[y - 1];
                y--;

                WW[y] = sy;
                count++;
            }
        }

        std::vector <bool> first(N);
        std::vector<std::pair<long long, std::pair<int, int>>> sec(N);
        std::multimap<long long, std::pair<int, int>> map = {};

        if (X > 0)
        {
            map.insert(std::make_pair(0LL + W[X - 1], std::make_pair(X - 1, -1)));
            first[X - 1] = true;
        }
        map.insert(std::make_pair(sx + W[x] - WW[x + 1], std::make_pair(x + 1, 1)));
        first[x] = true;
        if (Y + 1 < N)
        {
            map.insert(std::make_pair(0LL + W[Y], std::make_pair(Y + 1, 1)));
            first[Y + 1] = true;
        }
        map.insert(std::make_pair(sy + W[y - 1] - WW[y - 1], std::make_pair(y - 1, -1)));
        first[y] = true;

        while (map.size() > 0)
        {
            std::multimap<long long, std::pair<int, int>>::iterator it = map.lower_bound(-1);
            long long w = it->first;
            std::pair<int, int> ii = it->second;
            map.erase(it);

            sum += w;
            if (sum > K)
            {
                break;
            }

            if (ii.second == 1)
            {
                x = ii.first;
                w += WW[x];
                WW[x] = w;
                first[x] = false;
                if (sec[x].first != 0)
                {
                    map.insert(std::make_pair(sec[x].first - WW[x], sec[x].second));
                    sec[x].first = 0;
                }
                if (x + 1 < N)
                {
                    if (!first[x + 1])
                    {
                        map.insert(std::make_pair(w + W[x] - WW[x + 1], std::make_pair(x + 1, 1)));
                        first[x + 1] = true;

                    }
                    else
                    {
                        sec[x + 1] = std::make_pair(w + W[x], std::make_pair(x + 1, 1));
                    }
                }
            }
            else
            {
                y = ii.first;
                w += WW[y];
                WW[y] = w;
                first[y] = false;
                if (sec[y].first != 0)
                {
                    map.insert(std::make_pair(sec[y].first - WW[y], sec[y].second));
                    sec[y].first = 0;
                }
                if (y > 0)
                {
                    if (!first[y - 1])
                    {
                        map.insert(std::make_pair(w + W[y - 1] - WW[y - 1], std::make_pair(y - 1, -1)));
                        first[y - 1] = true;

                    }
                    else
                    {
                        sec[y - 1] = (std::make_pair(w + W[y - 1] - WW[y - 1], std::make_pair(y - 1, -1)));
                    }
                }
            }

            count++;
        }

        ans = std::max(ans, count);
    }

    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         if (a == i && b == i + 1 || b == i && a == i + 1)
      |             ~~^~~~
closing.cpp:55:25: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         if (a == i && b == i + 1 || b == i && a == i + 1)
      |                       ~~^~~~~~~~
closing.cpp:55:39: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         if (a == i && b == i + 1 || b == i && a == i + 1)
      |                                     ~~^~~~
closing.cpp:55:49: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         if (a == i && b == i + 1 || b == i && a == i + 1)
      |                                               ~~^~~~~~~~
closing.cpp:55:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   55 |         if (a == i && b == i + 1 || b == i && a == i + 1)
      |             ~~~~~~~^~~~~~~~~~~~~

• 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