Submission #671052

#	Time	Username	Problem	Language	Result	Execution time	Memory
671052		gavgav	Fountain (eJOI20_fountain)	C++17	100 / 100	115 ms	9164 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

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;
    }
};
int main(){
    // input
    int nodesNumber, pointsNumber;
    scanf("%d%d", &nodesNumber, &pointsNumber);
    int weightsSum[nodesNumber + 1] {0};
    int radii[nodesNumber + 1] {1000000001};
    for (int i = 1; i <= nodesNumber; ++i)
        scanf("%d%d", &(radii[i]), &(weightsSum[i]));

    // create tree
    int output[pointsNumber];
    int path[nodesNumber + 1] {0};
    int top = 0;
    vec <vec <point> > points (nodesNumber + 1);
    for (int i = 0; i < pointsNumber; ++i){
        int position, energy;
        scanf("%d%d", &position, &energy);
        points[position].puB(point {energy, i});
    }
    for (int i = 1; i <= nodesNumber; ++i){
        sort(points[i].begin(), points[i].end());
    }
    for (int i = nodesNumber; i > 0; --i){
        while (radii[path[top]] <= radii[i]){
            --top;
        }
        ++top;
        path[top] = i;
        weightsSum[path[top]] += weightsSum[path[top - 1]];
        int left, middle, right = top, answer;
        for (int j = 0; j < points[i].size(); ++j){
            left = 0, right = top;
            while (left <= right){
                middle = (left + right) / 2;
                if (weightsSum[path[top]] - weightsSum[path[middle]] < points[i][j].energy){
                    right = middle - 1;
                    answer = middle;
                }
                else{
                    left = middle + 1;
                }
            }
            output[points[i][j].id] = path[answer];
        }
    }
    for (int i = 0; i < pointsNumber; ++i)
        printf("%d\n", output[i]);
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int j = 0; j < points[i].size(); ++j){
      |                         ~~^~~~~~~~~~~~~~~~~~
fountain.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%d%d", &nodesNumber, &pointsNumber);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%d%d", &(radii[i]), &(weightsSum[i]));
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d%d", &position, &energy);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:57:50: warning: 'answer' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |             output[points[i][j].id] = path[answer];
      |                                       ~~~~~~~~~~~^

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