oj.uz

Submission #849827

# Submission time Handle Problem Language Result Execution time Memory
849827 2023-09-15T12:16:58 Z ogkostya Closing Time (IOI23_closing) C++17
8 / 100
 106 ms 31164 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4968 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 31164 KB Output is correct
2 Correct 87 ms 30908 KB Output is correct
3 Correct 61 ms 9296 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Incorrect 2 ms 5120 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Incorrect 2 ms 5120 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Incorrect 2 ms 5120 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4968 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4968 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4968 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4968 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4968 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -