# Untitled

unknown
c_cpp
3 years ago
2.8 kB
1
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
class Solution {
using llu = unsigned long long;
using ll = long long;
unordered_map<int, vector<int>> mapping;
void plan1(ll multiplies[], ll values[], llu& people_x, llu& people_n, const int target, llu multi) {
people_x += (multiplies[target] << multi) - multiplies[target];
people_n += (values[target] << multi) - values[target];
multiplies[target] <<= multi;
values[target] <<= multi;
}
void plan2(ll multiplies[], ll values[], llu& people_x, llu& people_n, const int target, ll multi) {
llu n = mapping[target].size();
bool is_3{multi < 0};
multi = abs(multi);
llu multi_diff = multiplies[target] * multi;
llu value_diff = values[target] * multi;
auto __plan2 = [&]() mutable {
people_x -= multi_diff * n;
people_n -= value_diff * n;
for (const auto& i : mapping[target]) {
multiplies[i] -= multi_diff;
values[i] -= value_diff;
}
};
auto __plan3 = [&]() mutable {
people_x += multi_diff * n;
people_n += value_diff * n;
for (const auto& i : mapping[target]) {
multiplies[i] += multi_diff;
values[i] += value_diff;
}
};
is_3 ? __plan3() : __plan2();
}
public:
vector<int> volunteerDeployment(vector<int>& finalCnt, long long totalNum, vector<vector<int>>& edges, vector<vector<int>>& plans) {
const int size = finalCnt.size() + 1;
for (const auto& edge : edges) {
mapping[edge[0]].emplace_back(edge[1]);
mapping[edge[1]].emplace_back(edge[0]);
}
ll multiplies[size], values[size];
memset(multiplies, 0, sizeof multiplies);
multiplies[0] = 1;
memset(values, 0, sizeof values);
auto tmp{values + 1};
llu people_n{0}, people_x{1};
for (const auto& i : finalCnt) {
*tmp++ = i;
people_n += i;
}
for (int i = plans.size() - 1; i >= 0; --i) {
int target = plans[i][1];
ll multi{1};
int j{i - 1};
switch (plans[i][0]) {
case 1: {
while (j >= 0 and target == plans[j][1] and plans[j][0] == 1) {
--j, ++multi;
}
plan1(multiplies, values, people_x, people_n, target, multi);
break;
}
case 3: multi = -1;
default: {
while (j >= 0 and target == plans[j][1] and plans[j][0] != 1) {
multi += plans[j--][0] == 2 ? 1 : -1;
}
if (multi != 0) {
plan2(multiplies, values, people_x, people_n, target, multi);
}
}
}
if (j != i - 1) {
i = j + 1;
}
}
int ans[size];
llu x{(static_cast<llu>(totalNum) - people_n) / people_x};
for (int i = 0; i < size; ++i) {
ans[i] = multiplies[i] * x + values[i];
}
return vector<int>(ans, ans + size);
}
};