Submission #1235136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235136		alexaaa	Closing Time (IOI23_closing)	C++20	0 / 100	59 ms	17984 KiB

closing

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Data{
    int n;
    int convenience_score = 2;
    vector<vector<pair<int, int>>> adj_list;
    long long t_w = 0;
    long long closing_time_sum = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> queue;
    vector<int> closing_time;
};

void traversal(vector<int> &cl_time, long long &cl_sum, long long K, long long total_weight, vector<vector<pair<int, int>>> &adj_list, int &convenience_score, int city, int prev_city, int other_city)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> queue;
    int prev = city;
    if (adj_list[city].empty())
    {
        return;
    }

    for (auto u : adj_list[city])
    {
        queue.push(u);
    }
    while (!queue.empty())
    {
        pair<int, int> v = queue.top();
        queue.pop();
        if (v.second == other_city)
        {
            return;
        }
        if (v.second == prev_city)
        {
            continue;
        }

        long long new_weight = total_weight + v.first;  
        cl_sum += new_weight;

     

        if (cl_sum <= K && cl_time[v.second] == 0)
        {
            cl_time[v.second] = v.first;
            convenience_score++;
            traversal(cl_time, cl_sum, K, new_weight, adj_list, convenience_score, v.second, prev, other_city);
        }
    
        else
        {
            cl_sum -= new_weight;

            if (cl_time[v.second])
            {
                if (new_weight <= cl_time[v.second])
                {
                    convenience_score++;
                }
                else
                {
                    int surplus = v.first - cl_time[v.second];
                    cl_sum += surplus;
                    cl_time[v.second] = v.first;
                    convenience_score++;
                }
            }

        }
    }
}

int  max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W){
    Data data;
    data.adj_list.resize(N);
    data.closing_time.resize(N);
    for (int i = 0; i < N; i++){
        data.adj_list[U[i]].push_back({W[i], V[i]});
        data.adj_list[V[i]].push_back({W[i], U[i]});
    }
    if (X != Y){
        traversal(data.closing_time, data.closing_time_sum, K, data.t_w, data.adj_list, data.convenience_score, X, X, Y);
        traversal(data.closing_time,data.closing_time_sum, K, data.t_w, data.adj_list, data.convenience_score, Y, Y, X);
    }
    else if (X == Y){
        data.convenience_score -= 1;
        traversal(data.closing_time,data.closing_time_sum, K, data.t_w, data.adj_list, data.convenience_score, X, X, Y);
    }
    return data.convenience_score;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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