#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
typedef long long ll;
int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w) {
priority_queue<pair<ll, ll>> finalQX, finalQY, doubleQ;
vector<vector<pair<ll, ll>>> adj(n);
for (int i = 0; i < w.size(); i++) {
adj[u[i]].push_back({-w[i], v[i]});
adj[v[i]].push_back({-w[i], u[i]});
}
vector<ll> distX(n, 1ll << 62ll), distY(n, 1ll << 62ll);
vector<bool> vstX(n), vstY(n);
priority_queue<pair<ll, ll>> q;
distX[x] = distY[y] = 0;
q.push({0, x});
while (!q.empty()) {
ll node = q.top().second; q.pop();
if (vstX[node]) continue;
vstX[node] = true;
for (auto &e : adj[node]) {
distX[e.second] = min(distX[e.second], distX[node] - e.first);
q.push({-distX[e.second], e.second});
}
}
q.push({0, y});
while (!q.empty()) {
ll node = q.top().second; q.pop();
if (vstY[node]) continue;
vstY[node] = true;
for (auto &e : adj[node]) {
distY[e.second] = min(distY[e.second], distY[node] - e.first);
q.push({-distY[e.second], e.second});
}
}
for (int i = 0; i < n; i++) {
finalQX.push({-distX[i], i});
finalQY.push({-distY[i], i});
doubleQ.push({-max(distX[i], distY[i]), i});
}
vstX = vector<bool>(n); vstY = vector<bool>(n);
ll res = 0;
while (!finalQX.empty() || !finalQY.empty() || !doubleQ.empty()) {
// Ensure no visited
ll t = finalQX.empty() ? 0 : finalQX.top().second;
while (vstX[t] && !finalQX.empty()) { finalQX.pop(); t = finalQX.top().second; }
t = finalQY.empty() ? 0 : finalQY.top().second;
while (vstY[t] && !finalQY.empty()) { finalQY.pop(); t = finalQY.top().second; }
t = doubleQ.empty() ? 0 : doubleQ.top().second;
while ((vstX[t] || vstY[t]) && !doubleQ.empty()) { doubleQ.pop(); t = doubleQ.top().second; }
if (!doubleQ.empty()) {
ll x2 = 1ll << 62ll, y2 = 1ll << 62ll, xy = 1ll << 62ll;
if (!finalQX.empty() && !finalQY.empty()) xy = -finalQX.top().first - finalQY.top().first;
if (finalQX.size() >= 2) {
auto i = finalQX.top(); finalQX.pop();
x2 = -i.first - finalQX.top().first;
finalQX.push(i);
}
if (finalQY.size() >= 2) {
auto i = finalQY.top(); finalQY.pop();
y2 = -i.first - finalQY.top().first;
finalQY.push(i);
}
ll dub = -doubleQ.top().first;
if (dub < x2 && dub < y2 && dub < xy && dub <= k) {
auto node = doubleQ.top(); doubleQ.pop();
vstX[node.second] = vstY[node.second] = true;
k -= dub;
res += 2;
continue;
}
}
if (finalQX.empty() && finalQY.empty()) break;
ll x1 = 1ll << 62ll, y1 = 1ll << 62ll;
if (!finalQX.empty()) x1 = -finalQX.top().first;
if (!finalQY.empty()) y1 = -finalQY.top().first;
if (x1 < y1) { // X
auto node = finalQX.top();
ll dist = -node.first; finalQX.pop();
if (dist > k) break;
vstX[node.second] = true;
if (!vstY[node.second]) finalQY.push({-abs(distX[node.second] - distY[node.second]), node.second});
k -= dist;
res++;
}
else { // Y
auto node = finalQY.top();
ll dist = -node.first; finalQY.pop();
if (dist > k) break;
vstY[node.second] = true;
if (!vstX[node.second]) finalQX.push({-abs(distX[node.second] - distY[node.second]), node.second});
k -= dist;
res++;
}
}
return res;
}
Compilation message
closing.cpp: In function 'int max_score(int, int, int, ll, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | for (int i = 0; i < w.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
36508 KB |
Output is correct |
| 2 |
Correct |
91 ms |
35612 KB |
Output is correct |
| 3 |
Correct |
69 ms |
2980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
