Submission #839886

#	Time	Username	Problem	Language	Result	Execution time	Memory
839886		Enchom	Closing Time (IOI23_closing)	C++17	0 / 100	53 ms	9932 KiB

closing

#include "closing.h"
#include <vector>
#include <queue>
using namespace std;
typedef long long llong;

vector<llong> Xdist;
vector<llong> Ydist;
vector<llong> c;
int n;
vector<vector<pair<int, llong>>> Graph;
int X, Y;
llong K;

struct Event
{
    int ver;
    int tp;
    llong cost;

    Event(int a, int b, llong c): ver(a), tp(b), cost(c) {}

    bool operator<(const Event& other) const
    {
        return cost > other.cost;
    }
};
int solveDisjoint()
{
    llong curTotal = 0;
    int score = 0;

    priority_queue<Event> eq;
    vector<bool> covered[2];

    covered[0].resize(n + 1, false);
    covered[1].resize(n + 1, false);

    eq.push(Event(X, 0, 0));
    eq.push(Event(Y, 0, 0));

    while(!eq.empty())
    {
        Event e = eq.top();
        eq.pop();

        if (curTotal + e.cost > K)
            break;

        score++;
        covered[e.tp][e.ver] = true;

        for (auto [nver, w] : Graph[e.ver])
        {
            if (covered[e.tp][nver])
                continue;

            eq.push(Event(nver, e.tp, e.cost + w));
        }
    }

    return score;
}

void refreshData()
{
    Xdist.clear();
    Ydist.clear();
    Graph.clear();
    c.clear();

    Xdist.resize(n + 1);
    Ydist.resize(n + 1);
    Graph.resize(n + 1);
    c.resize(n + 1);
}

void getDistances(int ver, int dad, vector<llong>& dst, llong curDist)
{
    for (auto [nver, w] : Graph[ver])
    {
        if (nver == dad)
            continue;

        getDistances(nver, ver, dst, curDist + w);
    }
}

int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    refreshData();
    n = N;
    ::X = X;
    ::Y = Y;
    ::K = K;

    for (int i = 0; i < n; i++)
    {
        c[i] = 0;
        Graph[U[i]].push_back({V[i], W[i]});
        Graph[V[i]].push_back({U[i], W[i]});
    }

    getDistances(X, 0, Xdist, 0);
    getDistances(Y, 0, Ydist, 0);

    return solveDisjoint();

    llong ans = solveDisjoint();

    /*
    llong xyDistance = Xdist[Y];

    for (int i = 0; i < n; i++)
    {
        if (Xdist[i] + Ydist[i] == xyDistance) /// On path
        {
            if (Xdist[i] <= Ydist[i])
        }
    }
    */

    return 0;
}

Compilation message (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:109:11: warning: unused variable 'ans' [-Wunused-variable]
  109 |     llong ans = solveDisjoint();
      |           ^~~

• 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