oj.uz

Submission #983403

# Submission time Handle Problem Language Result Execution time Memory
983403 2024-05-15T12:01:59 Z raphaelp Beads and wires (APIO14_beads) C++14
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;
void dfs(long long x, long long p, vector<long long> &wire, vector<long long> &nowire, vector<vector<pair<long long, long long>>> &AR, vector<long long> &up)
{
    long long sum = 0, best1 = -1234567890, best2 = -1234567890;
    for (long long i = 0; i < AR[x].size(); i++)
    {
        if (AR[x][i].first == p)
        {
            up[x] = AR[x][i].second;
            continue;
        }
        dfs(AR[x][i].first, x, wire, nowire, AR, up);
        sum += wire[AR[x][i].first];
        long long temp = nowire[AR[x][i].first] - wire[AR[x][i].first] + up[AR[x][i].first];
        if (temp > best1)
            swap(best1, temp);
        if (temp > best2)
            swap(best2, temp);
    }
    if (AR[x].size() > 2)
        nowire[x] = sum + best1 + best2;
    if (AR[x].size() > 1 && x != 0)
        wire[x] = sum + best1 + up[x];
    wire[x] = max(wire[x], nowire[x]);
}
int main()
{
    long long N;
    cin >> N;
    vector<vector<pair<long long, long long>>> AR(N);
    for (long long i = 0; i < N - 1; i++)
    {
        long long a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        AR[a].push_back({b, c});
        AR[b].push_back({a, c});
    }
    vector<long long> wire(N), nowire(N), up(N);
    dfs(0, 0, wire, nowire, AR, up);
    cout << wire[0];
}

Compilation message

beads.cpp: In function 'void dfs(long long int, long long int, std::vector<long long int>&, std::vector<long long int>&, std::vector<std::vector<std::pair<long long int, long long int> > >&, std::vector<long long int>&)':
beads.cpp:6:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |     for (long long i = 0; i < AR[x].size(); 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 Incorrect 0 ms 348 KB Output isn't correct
4 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 Incorrect 0 ms 348 KB Output isn't correct
4 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 Incorrect 0 ms 348 KB Output isn't correct
4 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 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -