제출 #670430

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
670430		gavgav	Fountain (eJOI20_fountain)	C++17	0 / 100	658 ms	524288 KiB

fountain

#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]);
}

컴파일 시 표준 에러 (stderr) 메시지

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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40