vector Conn[nm];
int n;
int Sm[nm];
int Q[nm];
int Dis[nm];
void init(int N, int mParent[], int mDistance[], int mQuantity[])
{
n = N;
for (int i = 0; i < nm; i++) {
Conn[i].clear();
}
for (int i = 0; i < N; i++) {
Conn[i].push_back(mParent[i]);
if (mParent[i] != -1) {
Conn[mParent[i]].push_back(i);
}
Q[i] = mQuantity[i];
Dis[i] = mDistance[i];
}
for (int i = N - 1; i >= 0; i--) {
Sm[i] = mQuantity[i];
for (int j = 1; j < Conn[i].size(); j++) {
Sm[i] += Sm[Conn[i][j]];
}
}
}
int carry(int mFrom, int mTo, int mQuantity)
{
int a1 = mFrom, a2 = mTo;
int sm = 0;
vector A1; vector A2;
while (a1 != a2) {
if (a1 > a2) {
A1.push_back(a1);
sm += Dis[a1];
a1 = Conn[a1][0];
}
else {
A2.push_back(a2);
sm += Dis[a2];
a2 = Conn[a2][0];
}
}
for (auto i : A1) {
Sm[i] -= mQuantity;
}
for (auto i : A2) {
Sm[i] += mQuantity;
}
Q[mFrom] -= mQuantity;
Q[mTo] += mQuantity;
return sm * mQuantity;
}
int gather(int mID, int mQuantity)
{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector notTake(nm, -1);
for (int i : Conn[mID]) {
if (i < 0) continue;
if (i < mID) pq.push({ Dis[mID],i });
else pq.push({ Dis[i], i });
notTake[i] = mID;
}
int totQ = mQuantity;
int ans = 0;
while (totQ != 0) {
int val = pq.top().second;
int prevDis = pq.top().first;
int quan = min(totQ, Q[val]);
totQ -= quan;
ans += carry(val, mID, quan);
pq.pop();
for (int i : Conn[val]) {
if (i != notTake[val] && i != -1) {
if (i < val) pq.push({ prevDis + Dis[val],i });
else pq.push({ prevDis + Dis[i],i });
notTake[i] = val;
}
}
}
return ans;
}
qiaobaaa
commented
1 year ago
define nm 10500
include
include
include
include
using namespace std;
vector Conn[nm];
int n;
int Sm[nm];
int Q[nm];
int Dis[nm];
void init(int N, int mParent[], int mDistance[], int mQuantity[]) { n = N; for (int i = 0; i < nm; i++) { Conn[i].clear(); } for (int i = 0; i < N; i++) { Conn[i].push_back(mParent[i]); if (mParent[i] != -1) { Conn[mParent[i]].push_back(i); } Q[i] = mQuantity[i]; Dis[i] = mDistance[i]; } for (int i = N - 1; i >= 0; i--) { Sm[i] = mQuantity[i]; for (int j = 1; j < Conn[i].size(); j++) { Sm[i] += Sm[Conn[i][j]]; } } }
int carry(int mFrom, int mTo, int mQuantity) { int a1 = mFrom, a2 = mTo; int sm = 0; vector A1; vector A2;
while (a1 != a2) {
if (a1 > a2) {
A1.push_back(a1);
sm += Dis[a1];
a1 = Conn[a1][0];
}
else {
A2.push_back(a2);
sm += Dis[a2];
a2 = Conn[a2][0];
}
}
for (auto i : A1) {
Sm[i] -= mQuantity;
}
for (auto i : A2) {
Sm[i] += mQuantity;
}
Q[mFrom] -= mQuantity;
Q[mTo] += mQuantity;
return sm * mQuantity;
}
int gather(int mID, int mQuantity) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; vector notTake(nm, -1);
for (int i : Conn[mID]) {
if (i < 0) continue;
if (i < mID) pq.push({ Dis[mID],i });
else pq.push({ Dis[i], i });
notTake[i] = mID;
}
int totQ = mQuantity;
int ans = 0;
while (totQ != 0) {
int val = pq.top().second;
int prevDis = pq.top().first;
int quan = min(totQ, Q[val]);
totQ -= quan;
ans += carry(val, mID, quan);
pq.pop();
for (int i : Conn[val]) {
if (i != notTake[val] && i != -1) {
if (i < val) pq.push({ prevDis + Dis[val],i });
else pq.push({ prevDis + Dis[i],i });
notTake[i] = val;
}
}
}
return ans;
}
int sum(int mID) {
}