oj.uz

Submission #924017

# Submission time Handle Problem Language Result Execution time Memory
924017 2024-02-08T09:25:10 Z boris_mihov Designated Cities (JOI19_designated_cities) C++17
0 / 100
 2 ms 8540 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];
llong ifRoot[MAXN];
llong maxPath[MAXN];
llong maxPath2[MAXN];
int fromPath[MAXN];
int fromPath2[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)
{
    ifRoot[node] = sum;
    answer[1] = std::max(answer[1], ifRoot[node]);
    for (const auto &[u, a, b]  : g[node])
    {
        if (u == par)
        {
            continue;
        }

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

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

        findMaxPath(u, node);
        if (maxPath[node] < maxPath[u] + a)
        {
            fromPath2[node] = fromPath[node];
            fromPath[node] = fromPath[u];
            maxPath2[node] = maxPath[node];
            maxPath[node] = maxPath[u] + a;
        } else if (maxPath2[node] < maxPath[u] + a)
        {
            fromPath2[node] = fromPath[u];
            maxPath2[node] = maxPath[u] + a;
        }
    }
}

void solve()
{
    if (n == 2)
    {
        int min = std::min(g[1][0].a, g[1][0].b);
        answer[1] = min;
        answer[2] = 0;
        return;
    }

    int root = 1;
    while (root <= n && g[root].size() == 1)
    {
        root++;
    }

    assert(root <= n);
    sumUpDFS(root, 0);
    findOneAnswer(root, 0, sumUp);
    findMaxPath(root, 0);

    for (int i = 1 ; i <= n ; ++i)
    {
        answer[2] = std::max(answer[2], ifRoot[i] + maxPath[i] + maxPath2[i]);
    }
}

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 2 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

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

Subtask #6
0 / 44.0

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