Submission #983412

#	Time	Username	Problem	Language	Result	Execution time	Memory
983412		raphaelp	Beads and wires (APIO14_beads)	C++14	0 / 100	1 ms	348 KiB

beads

#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 = -123456789000000, best2 = -123456789000000;
    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);
    }
    nowire[x] = sum;
    if (AR[x].size() > 2)
        nowire[x] = max(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 (stderr)

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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43