Submission #894656

#	Time	Username	Problem	Language	Result	Execution time	Memory
894656		JeanBombeur	Closing Time (IOI23_closing)	C++17	0 / 100	130 ms	41984 KiB

closing

#include "closing.h"
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

//  <|°_°|>

//  M. Broccoli & JeanBombeur

const int MAX_NODES = 2e5;

struct event {
    long long cost;
    int node, id;
};

vector <pair <int, int>> Adj[MAX_NODES];

long long Dist[2][MAX_NODES];
bool Taken[2][MAX_NODES];

vector <int> Path;

priority_queue <event> Greedy;

bool operator<(event a, event b) {
    return a.cost > b.cost;
}

bool Dfs(int id, int node, int parent = -1, int target = -1) {
    for (pair <int, int> dest : Adj[node])
    {
        if (dest.first != parent)
        {
            Dist[id][dest.first] = Dist[id][node] + dest.second;
            if (Dfs(id, dest.first, node, target))
                target = node;
        }
    }
    if (node == target)
        Path.push_back(node);
    return node == target;
}

int RunSmart(int answer, int maxSum) {
    int last = 0;
    int sum = 0;
    while (!Greedy.empty())
    {
        auto [cost, node, id] = Greedy.top();
        Greedy.pop();
        if (id == 2)
        {
            if (Taken[0][node] || Taken[1][node])
                continue;
            cost *= 2;
            if ((sum += cost) <= maxSum)
            {
                answer += 2;
                Taken[0][node] = Taken[1][node] = 1;
            }
            else if (sum - last <= maxSum)
            {
                answer ++;
                break;
            }
            else
                break;
        }
        else
        {
            if (Taken[id][node])
                continue;
            if ((sum += cost) > maxSum)
                break;
            Taken[id][node] = 1;
            answer ++;
            if (!Taken[id ^ 1][node])
                Greedy.push({Dist[id ^ 1][node] - Dist[id][node], node, id ^ 1});
        }
        last = cost;
    }
    return answer;
}

int max_score(int nbNodes, int start1, int start2, long long maxSum,
    vector <int> Left, vector <int> Right, vector <int> Weight) {
    
    maxSum <<= 1;
    
    Path.clear();
    for (int i = 0; i < nbNodes; i ++)
        Adj[i].clear();
    for (int i = 0; i < nbNodes - 1; i ++)
    {
        Adj[Left[i]].emplace_back(Right[i], Weight[i] << 1);
        Adj[Right[i]].emplace_back(Left[i], Weight[i] << 1);
    }
    for (int id = 0; id < 2; id ++)
    {
        fill_n(Dist[id], nbNodes, 0LL);
        fill_n(Taken[id], nbNodes, 0);
        if (!id)
            Dfs(id, start1);
        else
            Dfs(id, start2, -1, start1);
    }
    
    int answer = 0;
    int sum = 0;
    int greed = 0;
    vector <long long> mini;
    for (int i = 0; i < nbNodes; i ++)
    {
        mini.push_back(Dist[0][i]);
        mini.push_back(Dist[1][i]);
    }
    sort(mini.begin(), mini.end());
    for (int a : mini)
        if ((sum += a) <= maxSum)
            greed ++;
    
    while (!Greedy.empty())
        Greedy.pop();
    sum = 0;
    for (int a : Path)
    {
        int id = Dist[0][a] > Dist[1][a];
        sum += Dist[id][a];
        answer ++;
        Taken[id][a] = 1;
        Greedy.push({Dist[id ^ 1][a] - Dist[id][a], a, id ^ 1});
    }
    if (sum > maxSum)
        return greed;
    
    for (int i = 0; i < nbNodes; i ++)
    {
        int id = Dist[0][i] > Dist[1][i];
        Greedy.push({Dist[id][i], i, id});
        Greedy.push({Dist[id ^ 1][i] / 2, i, 2});
    }
    
    return max(greed, RunSmart(answer, maxSum - sum));
}

• 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