oj.uz

Submission #946490

# Submission time Handle Problem Language Result Execution time Memory
946490 2024-03-14T17:15:55 Z n3rm1n Fireworks (APIO16_fireworks) C++17
0 / 100
 1 ms 348 KB 
/// 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(p[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 > g;
        for (long long i = n+1; i <= n+m; ++ i)
        {
            g.push_back(dist[i]);
        }
        long long ans = 1e18;
        for (long long i = 0; i < g.size(); ++ i)
            ans = min(ans, get_diff(g[i]));
        cout << ans << endl;
    }
    return 0;
}

Compilation message

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 < g.size(); ++ i)
      |                               ~~^~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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