oj.uz

Submission #924061

# Submission time Handle Problem Language Result Execution time Memory
924061 2024-02-08T10:47:32 Z boris_mihov Designated Cities (JOI19_designated_cities) C++17
16 / 100
 305 ms 65684 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;
};

struct SegmentTree
{
    struct Node
    {
        llong max;
        llong lazy;
        int idx;
    
        Node()
        {
            max = lazy = idx = 0;
        }

        friend Node operator + (const Node &left, const Node &right)
        {
            Node res;
            if (left.max > right.max)
            {
                res.max = left.max;
                res.idx = left.idx;
            } else
            {
                res.max = right.max;
                res.idx = right.idx;
            }
            
            return res;
        }
    };

    Node tree[4*MAXN];
    void push(int node, int l, int r)
    {
        if (tree[node].lazy == 0)
        {
            return;
        }

        tree[node].max -= tree[node].lazy;
        if (l < r)
        {
            tree[2*node].lazy += tree[node].lazy;
            tree[2*node + 1].lazy += tree[node].lazy;
        }

        tree[node].lazy = 0;
    }

    void build(int l, int r, int node, llong dists[], const std::vector <int> &tour)
    {
        if (l == r)
        {
            tree[node].max = dists[tour[l]];
            tree[node].idx = l;
            return;
        }

        int mid = (l + r) / 2;
        build(l, mid, 2*node, dists, tour);
        build(mid + 1, r, 2*node + 1, dists, tour);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    void update(int l, int r, int node, int queryL, int queryR, int queryVal)
    {
        push(node, l, r);
        if (queryR < l || r < queryL)
        {
            return;
        }

        if (queryL <= l && r <= queryR)
        {
            tree[node].lazy += queryVal;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        update(l, mid, 2*node, queryL, queryR, queryVal);
        update(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    void build(llong dists[], const std::vector <int> &tour)
    {
        build(0, n - 1, 1, dists, tour);
    }

    void update(int l, int r, int val)
    {
        update(0, n - 1, 1, l, r, val);
    }

    std::pair <llong, int> getMAX()
    {
        return {tree[1].max, tree[1].idx};
    }
};

llong sumUp;
llong sumOfAll;
llong dists[MAXN];
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];

int in[MAXN];
int out[MAXN];
SegmentTree tree;
std::vector <int> tour;

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;
        }
    }
}

int parent[MAXN];
int parentEdge[MAXN];
void buildDFS(int node, int par)
{
    parent[node] = par; 
    in[node] = tour.size();
    tour.push_back(node);

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

        // std::cout << "Edge: " << node << ' ' << u << ' ' << a << '\n';
        parentEdge[u] = a;
        dists[u] = dists[node] + a;
        buildDFS(u, node);
    }

    out[node] = tour.size() - 1;
}

bool vis[MAXN];
llong take()
{
    auto [max, idx] = tree.getMAX();
    // std::cout << "Take: " << max << ' ' << idx << '\n';
    if (max == 0)
    {
        return max;
    }

    int node = tour[idx];
    while (!vis[node])
    {
        tree.update(in[node], out[node], parentEdge[node]);
        vis[node] = true;
        node = parent[node];
    }

    return max;
}

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);

    root = -1;
    llong last = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        answer[2] = std::max(answer[2], ifRoot[i] + maxPath[i] + maxPath2[i]);
        if (answer[2] > last)
        {
            last = answer[2];
            root = i;
        }
    }

    assert(root != -1);
    buildDFS(root, 0);
    tree.build(dists, tour);

    vis[root] = true;
    // std::cout << "tour\n";
    // for (int i = 0 ; i < n ; ++i)
    // {
    //     std::cout << tour[i] << ' ';
    // }

    // std::cout << '\n';
    take();
    take();


    for (int i = 3 ; i <= n ; ++i)
    {
        answer[i] = answer[i - 1] + take();
    }
}

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 10 ms 29020 KB Output is correct
2 Correct 5 ms 31064 KB Output is correct
3 Correct 5 ms 31064 KB Output is correct
4 Correct 5 ms 31068 KB Output is correct
5 Correct 5 ms 31068 KB Output is correct
6 Incorrect 6 ms 31068 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29016 KB Output is correct
2 Correct 255 ms 53084 KB Output is correct
3 Correct 305 ms 63636 KB Output is correct
4 Correct 208 ms 51404 KB Output is correct
5 Correct 242 ms 53284 KB Output is correct
6 Correct 247 ms 54472 KB Output is correct
7 Correct 205 ms 53620 KB Output is correct
8 Correct 291 ms 64264 KB Output is correct
9 Correct 179 ms 54312 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29016 KB Output is correct
2 Correct 252 ms 52996 KB Output is correct
3 Correct 247 ms 65684 KB Output is correct
4 Correct 204 ms 51420 KB Output is correct
5 Correct 263 ms 53008 KB Output is correct
6 Correct 251 ms 54852 KB Output is correct
7 Correct 190 ms 53756 KB Output is correct
8 Correct 290 ms 60360 KB Output is correct
9 Correct 177 ms 53756 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 29020 KB Output is correct
2 Correct 5 ms 31064 KB Output is correct
3 Correct 5 ms 31064 KB Output is correct
4 Correct 5 ms 31068 KB Output is correct
5 Correct 5 ms 31068 KB Output is correct
6 Incorrect 6 ms 31068 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29016 KB Output is correct
2 Correct 255 ms 53084 KB Output is correct
3 Correct 305 ms 63636 KB Output is correct
4 Correct 208 ms 51404 KB Output is correct
5 Correct 242 ms 53284 KB Output is correct
6 Correct 247 ms 54472 KB Output is correct
7 Correct 205 ms 53620 KB Output is correct
8 Correct 291 ms 64264 KB Output is correct
9 Correct 179 ms 54312 KB Output is correct
10 Correct 5 ms 29016 KB Output is correct
11 Correct 252 ms 52996 KB Output is correct
12 Correct 247 ms 65684 KB Output is correct
13 Correct 204 ms 51420 KB Output is correct
14 Correct 263 ms 53008 KB Output is correct
15 Correct 251 ms 54852 KB Output is correct
16 Correct 190 ms 53756 KB Output is correct
17 Correct 290 ms 60360 KB Output is correct
18 Correct 177 ms 53756 KB Output is correct
19 Correct 5 ms 29020 KB Output is correct
20 Incorrect 276 ms 53184 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 29020 KB Output is correct
2 Correct 5 ms 31064 KB Output is correct
3 Correct 5 ms 31064 KB Output is correct
4 Correct 5 ms 31068 KB Output is correct
5 Correct 5 ms 31068 KB Output is correct
6 Incorrect 6 ms 31068 KB Output isn't correct
7 Halted 0 ms 0 KB -