Submission #946496

#	Time	Username	Problem	Language	Result	Execution time	Memory
946496		n3rm1n	Fireworks (APIO16_fireworks)	C++17	7 / 100	1 ms	760 KiB

fireworks

/// fireworks
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 5005;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long n, m;
long long p[MAXN], c[MAXN];
vector < pair < long long, long long > > g[MAXN];

void read()
{
    cin >> n >> m;
    for (long long i = 2; i <= n + m; ++ i)
    {
        cin >> p[i] >> c[i];
        g[p[i]].push_back(make_pair(i, c[i]));
    }
}

long long used[MAXN], dist[MAXN];

void dfs(long long beg, long long path)
{
    used[beg] = 1;
    dist[beg] = path;
    long long nb, nb_cost;
    for (long long i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i].first;
        nb_cost = g[beg][i].second;
        if(!used[nb])
            dfs(nb, path + nb_cost);
    }
}
long long get_diff(long long x)
{
    long long ans = 0;
    for (long long i = n+1; i <= n+m; ++ i)
        ans += max(dist[i], x) - min(dist[i], x);
    return ans;
}
int main()
{
    speed();

    read();
    dfs(1, 0);
    if(n == 1)
    {
        vector < long long > f;
        for (long long i = n+1; i <= n+m; ++ i)
        {
            f.push_back(dist[i]);
        }
        long long ans = 1e18;
        for (long long i = 0; i < f.size(); ++ i)
            ans = min(ans, get_diff(f[i]));
        cout << ans << endl;
    }
    return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(long long int, long long int)':
fireworks.cpp:33: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]
   33 |     for (long long i = 0; i < g[beg].size(); ++ i)
      |                           ~~^~~~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:62:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for (long long i = 0; i < f.size(); ++ i)
      |                               ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45