| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 842343 | flashmt | 봉쇄 시간 (IOI23_closing) | C++17 | 0 ms | 0 KiB |
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"
#ifdef LOCAL
#include "Debug.h"
#else
#define debug(...) 42
#endif
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const long long oo = 1LL << 62;
int n;
vector<pair<int, int>> a[N];
vector<long long> bfs(int s)
{
vector<long long> dist(n, -1);
queue<int> q;
dist[s] = 0;
q.push(s);
while (!empty(q))
{
int x = q.front();
q.pop();
for (auto [y, w] : a[x])
if (dist[y] < 0)
{
dist[y] = dist[x] + w;
q.push(y);
}
}
return dist;
}
int isLinear()
{
for (int i = 0; i + 1 < n; i++)
{
int isGood = 0;
for (auto [j, _] : a[i])
if (j == i + 1)
isGood = 1;
if (!isGood)
return 0;
}
return 1;
}
int max_score(int N, int A, int B, long long budget, vector<int> U, vector<int> V, vector<int> W)
{
n = N;
for (int i = 0; i < n; i++)
a[i].clear();
for (int i = 0; i < size(U); i++)
{
a[U[i]].push_back({V[i], W[i]});
a[V[i]].push_back({U[i], W[i]});
}
auto distA = bfs(A);
auto distB = bfs(B);
auto distAB = distA[B];
if (distAB > budget * 2)
{
vector<long long> allDists = distA;
for (auto d : distB)
allDists.push_back(d);
sort(begin(allDists), end(allDists));
int ans = 0;
for (auto d : allDists)
if (d <= budget)
{
ans++;
budget -= d;
}
return ans;
}
if (isLinear())
{
vector<long long> sumA(n), sumB(n), sumAB(n);
for (int i = A; i <= B; i++)
{
sumA[i] = distA[i];
sumAB[i] = max(distA[i], distB[i]);
if (i)
{
sumA[i] += sumA[i - 1];
sumAB[i] += sumAB[i - 1];
}
}
for (int i = B - 1; i >= A; i--)
sumB[i] = sumB[i + 1] + distB[i];
vector<pair<long long, int>> ext;
for (int i = 0; i < n; i++)
if (i < A) ext.push_back({distA[i], i});
else if (i > B) ext.push_back({distB[i], i});
vector<long long> costFor(n, oo);
costFor[0] = 0;
sort(begin(ext), end(ext));
for (int i = 0; i < size(ext); i++)
costFor[i + 1] = costFor[i] + ext[i].first;
int ans = 0;
for (int l = A; l <= B; l++)
for (int r = A; r <= B; r++)
{
long long cost = 0;
int curAns = l - A + 1 + B - r + 1;
if (l < r) cost = sumA[l] + sumB[r];
else
{
cost = sumAB[l];
if (r)
{
cost -= sumAB[r - 1];
cost += sumA[r - 1];
}
if (l + 1 < n)
cost += sumB[l + 1];
}
if (cost > budget)
continue;
if (l < B && r > A)
{
int u = upper_bound(begin(costFor), end(costFor), budget - cost) - begin(costFor);
curAns += u - 1;
}
else
{
long long rem = budget - cost;
int both = 0;
for (int i = 0; i < size(ext); i++)
{
auto [extCost, id] = ext[i];
while (both && extCost > distAB)
{
rem -= distAB;
if (rem < 0)
break;
curAns++;
both--;
}
rem -= extCost;
if (rem < 0)
break;
curAns++;
if (id < A && r == A) both++;
else if (id > B && l == B) both++;
}
if (rem >= 0)
curAns += min(int64_t(both), rem / distAB);
}
ans = max(ans, curAns);
}
return ans;
}
return 0;
}