oj.uz

Submission #991265

# Submission time Handle Problem Language Result Execution time Memory
991265 2024-06-01T16:54:33 Z canadavid1 Beads and wires (APIO14_beads) C++17
0 / 100
 0 ms 352 KB 
#include <iostream>
#include <vector>
#include <utility>
#include <functional>
using i64 = long long;
std::vector<std::vector<std::pair<int,int>>> neigh;



struct Node
{
    int w_up=0;
    std::vector<Node> ch;
    Node(int where, int prev)
    {
        for(auto[w,c] : neigh[where])
        {
            if(w==prev) w_up = c;
            else ch.emplace_back(w,where);
        }
    }
    // returns {cost if I manage the top edge (might not use it), 
    //          cost if you have the top edge (including edge)}
    // answer to problem is root.calculate_ms().second
    std::pair<int,int> calculate_ms() const
    {
        std::vector<std::pair<int,int>> cw;
        for(auto& i : ch) cw.push_back(i.calculate_ms());
        if(cw.size()==0) return {0,w_up};
        if(cw.size()==1)
        {
            auto[a,b] = cw[0];
            return {std::max(a,b+w_up),w_up+a};
        }
        long long s = 0;
        for(auto &[a,b] : cw) s+=a;
        std::vector<int> diff;
        for(int i = 0; i < cw.size(); i++) diff.push_back(cw[i].second-cw[i].first);
        int m = 0;
        for(int i = 1; i < diff.size(); i++) if (diff[i]>diff[m]) m = i;
        int m2 = !m;
        for(int i = 1; i < diff.size(); i++) if(i!=m && diff[i] > diff[m2]) m2 = i;
        auto with_two = diff[m]+diff[m2]+s;
        auto without = s;
        auto with_one = diff[m]+s+w_up;
        return {std::max(with_two,std::max(without,with_one)),w_up+std::max(with_two,without)};
    }
};



int main()
{
    int N;
    std::cin >> N;
    neigh.resize(N);
    for(int i = 0; i < N-1; i++)
    {
        int a,b,c;
        std::cin >> a >> b >> c;
        a--;b--;
        neigh[a].emplace_back(b,c);
        neigh[b].emplace_back(a,c);
    }
    Node tree(0,-1);
    std::cout << tree.calculate_ms().second << "\n";
}

Compilation message

beads.cpp: In member function 'std::pair<int, int> Node::calculate_ms() const':
beads.cpp:38:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int i = 0; i < cw.size(); i++) diff.push_back(cw[i].second-cw[i].first);
      |                        ~~^~~~~~~~~~~
beads.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int i = 1; i < diff.size(); i++) if (diff[i]>diff[m]) m = i;
      |                        ~~^~~~~~~~~~~~~
beads.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int i = 1; i < diff.size(); i++) if(i!=m && diff[i] > diff[m2]) m2 = i;
      |                        ~~^~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 352 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 352 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 352 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 352 KB Output isn't correct
7 Halted 0 ms 0 KB -