oj.uz

Submission #924021

# Submission time Handle Problem Language Result Execution time Memory
924021 2024-02-08T09:43:39 Z boris_mihov Designated Cities (JOI19_designated_cities) C++17
16 / 100
 180 ms 39620 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 sum = g[1][0].a + g[1][0].b;
        int max = std::max(g[1][0].a, g[1][0].b);
        answer[1] = max;
        answer[2] = sum;
        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 Correct 2 ms 8540 KB Output is correct
2 Incorrect 2 ms 10716 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 140 ms 25552 KB Output is correct
3 Correct 180 ms 36340 KB Output is correct
4 Correct 124 ms 24400 KB Output is correct
5 Correct 124 ms 25212 KB Output is correct
6 Correct 140 ms 27220 KB Output is correct
7 Correct 105 ms 25604 KB Output is correct
8 Correct 168 ms 36688 KB Output is correct
9 Correct 88 ms 26072 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 133 ms 26712 KB Output is correct
3 Correct 151 ms 39620 KB Output is correct
4 Correct 129 ms 25424 KB Output is correct
5 Correct 147 ms 26576 KB Output is correct
6 Correct 147 ms 28860 KB Output is correct
7 Correct 91 ms 26968 KB Output is correct
8 Correct 166 ms 34388 KB Output is correct
9 Correct 97 ms 26744 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 140 ms 25552 KB Output is correct
3 Correct 180 ms 36340 KB Output is correct
4 Correct 124 ms 24400 KB Output is correct
5 Correct 124 ms 25212 KB Output is correct
6 Correct 140 ms 27220 KB Output is correct
7 Correct 105 ms 25604 KB Output is correct
8 Correct 168 ms 36688 KB Output is correct
9 Correct 88 ms 26072 KB Output is correct
10 Correct 1 ms 8536 KB Output is correct
11 Correct 133 ms 26712 KB Output is correct
12 Correct 151 ms 39620 KB Output is correct
13 Correct 129 ms 25424 KB Output is correct
14 Correct 147 ms 26576 KB Output is correct
15 Correct 147 ms 28860 KB Output is correct
16 Correct 91 ms 26968 KB Output is correct
17 Correct 166 ms 34388 KB Output is correct
18 Correct 97 ms 26744 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Incorrect 131 ms 26628 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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