#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vec vector
#define puB push_back
#define poB pop_back
#define qu queue
/*
* This problem can be interpreted like that:
* Exist tree with N nodes (reservoirs) and Q points (one release of water from tap).
* Points
* each point at start appear somewhere in the tree and want to go to the root (waterways) node.
* point has energy (volume).
* Nodes
* node has 2 attributes - weight(capacity), how much energy need to escape this node
* and depth - distance from root.
* By the way tree isn't set explicitly, so by using radii of reservoirs you need to create it.
* Current node connected to the nearest lower with greater radius.
*
*
* What is going on when problem running: points goes to root but lose their energy,
* and when the current point's energy ended you print in which node that does happen.
*
*
* How do I solve this problem:
* The main idea don't go by the same edge twice => each edge will be used maximum 1 time.
* For make this I grouped (to sorted array or fibonacci heap) points that appear in the same node, I will call that bunch.
* Then I go 1 by 1 to each node from furthest to nearest (distance I called depth) and go to each bunch in this node
* (by the way in 1 node may be many bunches, 'cause some bunches come from further nodes when I checked they).
* When I will need to know which points hasn't enough energy in this bunch, to go to the next node I will check 1 by 1 each point from lower to greater,
* those who hasn't enough energy I delete and print in which node that does happen;
* those who have enough energy I leave and when I checked all points in bunch I will add this bunch in next node.
*
* Works with Q * log(Q) 'cause for sorting if array or for deleting in fibonacci heap(I will use array, it's easier;).
*/
struct node{
int depth = 0, weight;
bool operator < (node b){ // for sort
return this->depth >= b.depth;
}
};
struct point{
int energy, id; // id for at end print answers in right order
bool operator < (point b){ // for sort
return this->energy >= b.energy;
}
};
struct bunch{
int energyLost = 0;
vec <point> points;
};
int main(){
// input
int nodesNumber, pointsNumber;
scanf("%d%d", &nodesNumber, &pointsNumber);
node nodes[nodesNumber + 1]; // + 1 for waterways, and in another variables
int radii[nodesNumber + 1];
radii[0] = 1000000000 + 1;
for (int i = 1; i <= nodesNumber; ++i)
scanf("%d%d", &(radii[i]), &(nodes[i].weight));
// create tree
int links[nodesNumber + 1]; // connections in tree
int greaterNode[nodesNumber + 1] {0}; // I will use like stack, at start add waterways
int top = 0;
for (int i = nodesNumber; i > 0; --i){
while (radii[greaterNode[top]] <= radii[i]){
--top;
}
links[i] = greaterNode[top];
nodes[i].depth = nodes[greaterNode[top]].depth + 1;
++top;
greaterNode[top] = i;
}
// putting signals in their place in tree
vec <vec <bunch>> bunches (nodesNumber + 1, vec <bunch> (1));
for (int i = 0; i < pointsNumber; ++i){
int position, energy;
scanf("%d%d", &position, &energy);
bunches[position][0].points.puB(point {energy, i});
}
sort(nodes, nodes + nodesNumber + 1);
// running solution
for (int i = 0; i < nodesNumber; ++i){
for (int j = 0; j < bunches[i].size(); ++j){
sort(bunches[i][j].points.begin(), bunches[i][j].points.end());
}
}
int output[pointsNumber];
for (int i = 1; i <= nodesNumber; ++i){
for (int j = 0; j < bunches[i].size(); ++j){
bunch current = bunches[i][j];
for (int k = current.points.size() - 1; k > -1 && current.points[k].energy - current.energyLost <= nodes[i].weight; --k) {
output[current.points[k].id] = i;
current.points.poB();
}
if(current.points.size() > 0){
current.energyLost += nodes[i].weight;
bunches[links[i]].puB(current);
}
}
}
for (int i = 0; i < pointsNumber; ++i)
printf("%d\n", output[i]);
}
Compilation message
fountain.cpp: In function 'int main()':
fountain.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bunch>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int j = 0; j < bunches[i].size(); ++j){
| ~~^~~~~~~~~~~~~~~~~~~
fountain.cpp:104:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bunch>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for (int j = 0; j < bunches[i].size(); ++j){
| ~~^~~~~~~~~~~~~~~~~~~
fountain.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | scanf("%d%d", &nodesNumber, &pointsNumber);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d%d", &(radii[i]), &(nodes[i].weight));
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%d%d", &position, &energy);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
658 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
