oj.uz

Submission #839886

# Submission time Handle Problem Language Result Execution time Memory
839886 2023-08-30T19:32:11 Z Enchom Closing Time (IOI23_closing) C++17
0 / 100
 53 ms 9932 KB 
#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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 9932 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -