This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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, long long>> 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, long long> 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, long long maxSum) {
int last = 0;
long long 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;
long long 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 (long long 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));
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |