#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
typedef long long ll;
int max_score_seperate(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});
}
}
finalQX.push({0, x});
finalQY.push({0, y});
vstX = vector<bool>(n); vstY = vector<bool>(n);
vector<bool> nbX(n), nbY(n);
nbX[x] = nbY[y] = true;
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();
t = finalQX.top().second;
while (vstX[t] && !finalQX.empty()) { finalQX.pop(); t = finalQX.top().second; }
if (finalQX.empty()) { finalQX.push(i); goto skipX; }
x2 = -i.first - finalQX.top().first;
finalQX.push(i);
}
skipX:
if (finalQY.size() >= 2) {
auto i = finalQY.top(); finalQY.pop();
t = finalQY.top().second;
while (vstY[t] && !finalQY.empty()) { finalQY.pop(); t = finalQY.top().second; }
if (finalQY.empty()) { finalQY.push(i); goto skipY; }
y2 = -i.first - finalQY.top().first;
finalQY.push(i);
}
skipY:
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;
for (auto &e : adj[node.second]) {
nbX[e.second] = nbY[e.second] = true;
finalQX.push({-(vstY[e.second] ? abs(distX[e.second] - distY[e.second]) : distX[e.second]), e.second});
finalQY.push({-(vstX[e.second] ? abs(distX[e.second] - distY[e.second]) : distY[e.second]), e.second});
doubleQ.push({-max(distX[e.second], distY[e.second]), e.second});
}
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;
for (auto &e : adj[node.second]) {
nbX[e.second] = true;
finalQX.push({-(vstY[e.second] ? abs(distX[e.second] - distY[e.second]) : distX[e.second]), e.second});
if (nbY[e.second]) doubleQ.push({-max(distX[e.second], distY[e.second]), e.second});
}
if (!vstY[node.second] && nbY[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;
for (auto &e : adj[node.second]) {
nbY[e.second] = true;
finalQY.push({-(vstX[e.second] ? abs(distX[e.second] - distY[e.second]) : distY[e.second]), e.second});
if (nbX[e.second]) doubleQ.push({-max(distX[e.second], distY[e.second]), e.second});
}
if (!vstX[node.second] && nbX[node.second]) finalQX.push({-abs(distX[node.second] - distY[node.second]), node.second});
k -= dist;
res++;
}
}
return res;
}
int max_score_meet(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});
}
}
finalQX.push({0, x});
finalQY.push({0, y});
vstX = vector<bool>(n); vstY = vector<bool>(n);
vector<bool> nbX(n), nbY(n);
nbX[x] = nbY[y] = true;
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();
t = finalQX.top().second;
while (vstX[t] && !finalQX.empty()) { finalQX.pop(); t = finalQX.top().second; }
if (finalQX.empty()) goto skipX1;
x2 = -i.first - finalQX.top().first;
finalQX.push(i);
}
skipX1:
if (finalQY.size() >= 2) {
auto i = finalQY.top(); finalQY.pop();
t = finalQY.top().second;
while (vstY[t] && !finalQY.empty()) { finalQY.pop(); t = finalQY.top().second; }
if (finalQY.empty()) goto skipY1;
y2 = -i.first - finalQY.top().first;
finalQY.push(i);
}
skipY1:
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;
for (auto &e : adj[node.second]) {
nbX[e.second] = nbY[e.second] = true;
finalQX.push({-(vstY[e.second] ? abs(distX[e.second] - distY[e.second]) : distX[e.second]), e.second});
finalQY.push({-(vstX[e.second] ? abs(distX[e.second] - distY[e.second]) : distY[e.second]), e.second});
doubleQ.push({-max(distX[e.second], distY[e.second]), e.second});
}
k -= dub;
res += 2;
break;
}
}
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;
for (auto &e : adj[node.second]) {
if (distY[e.second] > distY[node.second]) continue;
nbX[e.second] = true;
finalQX.push({-(vstY[e.second] ? abs(distX[e.second] - distY[e.second]) : distX[e.second]), e.second});
if (nbY[e.second]) doubleQ.push({-max(distX[e.second], distY[e.second]), e.second});
}
if (!vstY[node.second] && nbY[node.second]) finalQY.push({-abs(distX[node.second] - distY[node.second]), node.second});
k -= dist;
res++;
if (vstY[node.second]) break;
}
else { // Y
auto node = finalQY.top();
ll dist = -node.first; finalQY.pop();
if (dist > k) break;
vstY[node.second] = true;
for (auto &e : adj[node.second]) {
if (distX[e.second] > distX[node.second]) continue;
nbY[e.second] = true;
finalQY.push({-(vstX[e.second] ? abs(distX[e.second] - distY[e.second]) : distY[e.second]), e.second});
if (nbX[e.second]) doubleQ.push({-max(distX[e.second], distY[e.second]), e.second});
}
if (!vstX[node.second] && nbX[node.second]) finalQX.push({-abs(distX[node.second] - distY[node.second]), node.second});
k -= dist;
res++;
if (vstX[node.second]) break;
}
}
for (int i = 0; i < n; i++) {
if (vstX[i]) {
for (auto &e : adj[i]) {
nbX[e.second] = true;
finalQX.push({-(vstY[e.second] ? abs(distX[e.second] - distY[e.second]) : distX[e.second]), e.second});
if (nbY[e.second]) doubleQ.push({-max(distX[e.second], distY[e.second]), e.second});
}
}
if (vstY[i]) {
for (auto &e : adj[i]) {
nbY[e.second] = true;
finalQY.push({-(vstX[e.second] ? abs(distX[e.second] - distY[e.second]) : distY[e.second]), e.second});
if (nbX[e.second]) doubleQ.push({-max(distX[e.second], distY[e.second]), e.second});
}
}
}
for (int i = 0; i < n; i++) {
if (vstX[i]) {
if (!vstY[i] && nbY[i]) finalQY.push({-abs(distX[i] - distY[i]), i});
}
if (vstY[i]) {
if (!vstX[i] && nbX[i]) finalQX.push({-abs(distX[i] - distY[i]), i});
}
}
////////////////////////////////////////
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();
t = finalQX.top().second;
while (vstX[t] && !finalQX.empty()) { finalQX.pop(); t = finalQX.top().second; }
if (finalQX.empty()) goto skipX;
x2 = -i.first - finalQX.top().first;
finalQX.push(i);
}
skipX:
if (finalQY.size() >= 2) {
auto i = finalQY.top(); finalQY.pop();
t = finalQY.top().second;
while (vstY[t] && !finalQY.empty()) { finalQY.pop(); t = finalQY.top().second; }
if (finalQY.empty()) goto skipY;
y2 = -i.first - finalQY.top().first;
finalQY.push(i);
}
skipY:
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;
for (auto &e : adj[node.second]) {
nbX[e.second] = nbY[e.second] = true;
finalQX.push({-(vstY[e.second] ? abs(distX[e.second] - distY[e.second]) : distX[e.second]), e.second});
finalQY.push({-(vstX[e.second] ? abs(distX[e.second] - distY[e.second]) : distY[e.second]), e.second});
doubleQ.push({-max(distX[e.second], distY[e.second]), e.second});
}
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;
for (auto &e : adj[node.second]) {
nbX[e.second] = true;
finalQX.push({-(vstY[e.second] ? abs(distX[e.second] - distY[e.second]) : distX[e.second]), e.second});
if (nbY[e.second]) doubleQ.push({-max(distX[e.second], distY[e.second]), e.second});
}
if (!vstY[node.second] && nbY[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;
for (auto &e : adj[node.second]) {
nbY[e.second] = true;
finalQY.push({-(vstX[e.second] ? abs(distX[e.second] - distY[e.second]) : distY[e.second]), e.second});
if (nbX[e.second]) doubleQ.push({-max(distX[e.second], distY[e.second]), e.second});
}
if (!vstX[node.second] && nbX[node.second]) finalQX.push({-abs(distX[node.second] - distY[node.second]), node.second});
k -= dist;
res++;
}
}
return res;
}
int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w) {
if (k > 10000) k++;
ll sep = max_score_seperate(n, x, y, k, u, v, w);
ll meet = max_score_meet(n, x, y, k, u, v, w);
ll res = max(sep, meet);
return res;
}
Compilation message
closing.cpp: In function 'int max_score_seperate(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++) {
| ~~^~~~~~~~~~
closing.cpp: In function 'int max_score_meet(int, int, int, ll, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:139:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for (int i = 0; i < w.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
25680 KB |
Output is correct |
| 2 |
Correct |
123 ms |
25888 KB |
Output is correct |
| 3 |
Correct |
75 ms |
2908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '31' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '31' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '31' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '31' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '31' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '31' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '31' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '31' |
| 4 |
Halted |
0 ms |
0 KB |
- |
