oj.uz

Submission #924014

# Submission time Handle Problem Language Result Execution time Memory
924014 2024-02-08T09:14:29 Z boris_mihov Designated Cities (JOI19_designated_cities) C++17
7 / 100
 135 ms 30292 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 200000 + 10;
const int INF  = 1e9;

int n, q;
struct Edge
{
    int u, a, b;
};

llong sumUp;
llong sumOfAll;
llong answer[MAXN];
std::vector <Edge> g[MAXN];
int sz[MAXN];

void sumUpDFS(int node, int par)
{
    sz[node] = 1;
    for (const auto &[u, a, b] : g[node])
    {
        if (u == par)
        {
            continue;
        }

        sumUp += b;
        sumUpDFS(u, node);
        sz[node] += sz[u];
    }
}

void findOneAnswer(int node, int par, llong sum)
{
    answer[1] = std::max(answer[1], sum);
    for (const auto &[u, a, b]  : g[node])
    {
        if (u == par)
        {
            continue;
        }

        findOneAnswer(u, node, sum + a - b);
    }
}

void solve()
{
    sumUpDFS(1, 0);
    findOneAnswer(1, 0, sumUp);
}

void input()
{
    std::cin >> n;
    for (int i = 1 ; i < n ; ++i)
    {
        int u, v, a, b;
        std::cin >> u >> v >> a >> b;
        g[u].push_back({v, a, b});
        g[v].push_back({u, b, a});
        sumOfAll += a;
        sumOfAll += b;
    }

    std::cin >> q;
}

void print()
{
    for (int i = 1 ; i <= q ; ++i)
    {
        int cnt;
        std::cin >> cnt;
        std::cout << sumOfAll - answer[cnt] << '\n';
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();
    print();

    return 0;   
}

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 113 ms 21340 KB Output is correct
3 Correct 135 ms 29828 KB Output is correct
4 Correct 95 ms 19796 KB Output is correct
5 Correct 101 ms 21112 KB Output is correct
6 Correct 111 ms 22796 KB Output is correct
7 Correct 91 ms 21252 KB Output is correct
8 Correct 134 ms 30292 KB Output is correct
9 Correct 75 ms 21760 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 113 ms 21340 KB Output is correct
3 Correct 135 ms 29828 KB Output is correct
4 Correct 95 ms 19796 KB Output is correct
5 Correct 101 ms 21112 KB Output is correct
6 Correct 111 ms 22796 KB Output is correct
7 Correct 91 ms 21252 KB Output is correct
8 Correct 134 ms 30292 KB Output is correct
9 Correct 75 ms 21760 KB Output is correct
10 Incorrect 2 ms 6588 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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