oj.uz

Submission #597920

# Submission time Handle Problem Language Result Execution time Memory
597920 2022-07-17T07:23:17 Z web Chase (CEOI17_chase) C++17
0 / 100
 4000 ms 9548 KB 
#include <numeric>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


vector<long> cumulativeNeighbourPigs;
void init(vector<long>& pigs, vector<vector<int>>& adj)
{
    cumulativeNeighbourPigs.resize(pigs.size());
    for(int i = 0; i<pigs.size(); ++i)
    {
        for(auto child : adj[i])
        {
            cumulativeNeighbourPigs[i] += pigs[child];
        }
    }
}
long DFS(int startNode, vector<vector<int>>& adj, vector<long>& pig, int depth, const int v, long currP)
{
   
    if(depth == v)
    {
        return currP;
    }
    else
    {
        if(depth > v)
            return -1;
        else
        {
            long currMax = 0;
            for(auto child : adj[startNode])
            {
              //  cout<<"trying child: "<<child<<endl;
                long childPigeons = cumulativeNeighbourPigs[child] - pig[startNode];
                childPigeons = DFS(child, adj, pig, depth+1, v, currP+ childPigeons);
                if(currMax < childPigeons)
                    currMax = childPigeons;
               // cout<<"new max "<<currMax<<endl;
            }
            return max(currP, currMax);
        }
    }
}

long maxPigeonsPath(vector<vector<int>>& adj, vector<long>& pig, const int v)
{
    long maxP = 0;
    for(int i  =0 ;i<adj.size(); ++i)
    {
        long pigs = DFS(i, adj, pig, 1, v, cumulativeNeighbourPigs[i]);
        if(pigs > maxP)
            maxP = pigs;
    }
    return maxP;
}

int main()
{
    
    int n; cin>>n;
    int v; cin>>v;
    vector<long> pigeons(n);
    for(int i =0; i<n; ++i)
        cin>>pigeons[i];

    vector<vector<int>> adjList(n);
    for(int i = 0; i<n-1; ++i)
    {
        int a, b; 
        cin>>a>>b;
        adjList[a-1].push_back(b-1);
        adjList[b-1].push_back(a-1);
    }  
    init(pigeons, adjList);
    cout<<maxPigeonsPath(adjList, pigeons, v)<<endl;


    return 0;
}

Compilation message

chase.cpp: In function 'void init(std::vector<long int>&, std::vector<std::vector<int> >&)':
chase.cpp:13:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i = 0; i<pigs.size(); ++i)
      |                    ~^~~~~~~~~~~~
chase.cpp: In function 'long int maxPigeonsPath(std::vector<std::vector<int> >&, std::vector<long int>&, int)':
chase.cpp:52:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i  =0 ;i<adj.size(); ++i)
      |                    ~^~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4054 ms 9548 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -