oj.uz

Submission #946496

# Submission time Handle Problem Language Result Execution time Memory
946496 2024-03-14T17:18:40 Z n3rm1n Fireworks (APIO16_fireworks) C++17
7 / 100
 1 ms 760 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(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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 760 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 760 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 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 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 760 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -