Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
4.5 kB
4
Indexable
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<cstring>
using namespace std;
struct Node
{
    int id;
    int par;
    vector<int>child;
    int dis;
    int level;
    int dsum;
    int quantity;
}pool[10009];
int poolsize;
void init(int N, int mParent[], int mDistance[], int mQuantity[])
{
    poolsize = N;
    pool[0].id = 0;
    pool[0].par = -1;
    pool[0].dis = -1;
    pool[0].quantity = mQuantity[0];
    pool[0].child.clear();
    pool[0].level = 1;
    pool[0].dsum = mQuantity[0];
 
    for (int i = 1; i < poolsize; i++)
    {
        pool[i].id = i;
        pool[i].par = mParent[i];
        pool[mParent[i]].child.push_back(i);
        pool[i].dis = mDistance[i];
        pool[i].quantity = mQuantity[i];
        pool[i].child.clear();
        pool[i].dsum = mQuantity[i];
        pool[i].level = pool[mParent[i]].level + 1;
        int parentId = mParent[i];
        while (parentId != -1)
        {
            pool[parentId].dsum += mQuantity[i];
            parentId = pool[parentId].par;
        }
    }
}
 
int carry(int mFrom, int mTo, int mQuantity)
{
    int start = pool[mFrom].id;
    int end = pool[mTo].id;
    pool[start].quantity -= mQuantity;
    pool[end].quantity += mQuantity;
 
    int cost = 0;
    while (start != end)
    {
        if (pool[start].level > pool[end].level)
        {
            pool[start].dsum -= mQuantity;
            cost += pool[start].dis;
            start = pool[start].par;
        }
        else if (pool[start].level < pool[end].level) {
             
            pool[end].dsum += mQuantity; 
            cost += pool[end].dis;
             
            end = pool[end].par;
        }
 
        else {
            pool[start].dsum -= mQuantity;
            cost += pool[start].dis;
            start = pool[start].par;
 
            pool[end].dsum += mQuantity;
            cost += pool[end].dis;
            end= pool[end].par;
 
        }
 
    }
    return cost* mQuantity;
}
 
int gather(int mID, int mQuantity)
{
    int cost = 0;
    int vis[10009];
    int quant = mQuantity;
    memset(vis, 0, sizeof(vis));
    pool[mID].quantity += mQuantity;
    vis[mID] = 1;
    vector<pair<int, int>> pendingUpdate;
    //pair distance and id
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i = 0; i < pool[mID].child.size(); i++) {
        int childId = pool[mID].child[i];
        int distance = pool[childId].dis;
        pq.push({ distance, childId });
        vis[childId] = 1;
    }
 
    if (pool[mID].par != -1) {
        pq.push({ pool[mID].dis, pool[mID].par });
        vis[pool[mID].par] = 1;
    }
    while (pq.empty() == false) {
        auto x = pq.top();
        pq.pop();
        int currentQuantity = pool[x.second].quantity;
        int currentDistance = x.first;
        int currentId = x.second;
 
        if (currentQuantity < mQuantity) {
 
            pool[currentId].quantity = 0;
            mQuantity -= currentQuantity;
 
            cost += currentQuantity * currentDistance;
            pendingUpdate.push_back({ currentId, -currentQuantity });
 
            for (int i = 0; i < pool[currentId].child.size(); i++) {
                int childId = pool[currentId].child[i];
                if (vis[childId] == 0) {
                    vis[childId] = 1;
                    pq.push({ currentDistance + pool[childId].dis, childId });
                }
            }
            int parentId = pool[currentId].par;
            if (parentId != -1 && vis[parentId] == 0) {
                vis[parentId] = 1;
                pq.push({ currentDistance + pool[currentId].dis, parentId });
            }
        }
        else {
            pool[currentId].quantity -= mQuantity;
            pendingUpdate.push_back({ currentId, -mQuantity });
            cost += mQuantity * currentDistance;
            break;
        }
    }
 
    pendingUpdate.push_back({ mID, quant });
    for (int i = 0; i < pendingUpdate.size(); i++) {
 
        int currentId = pendingUpdate[i].first;
        int distanceToBeModified = pendingUpdate[i].second;
        while (currentId != -1) {
            pool[currentId].dsum += distanceToBeModified;
            currentId = pool[currentId].par;
        }
    }
 
 
    return cost;
}
 
int sum(int mID)
{
     return pool[mID].dsum;;
}