oj.uz

Submission #924066

# Submission time Handle Problem Language Result Execution time Memory
924066 2024-02-08T11:01:46 Z boris_mihov Designated Cities (JOI19_designated_cities) C++17
16 / 100
 349 ms 69564 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
#define int long long
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 << ' ' << tour[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);
    assert(tour.size() == n);
    tree.build(dists, tour);

    vis[root] = true;
    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);
}

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

    return 0;   
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from designated_cities.cpp:4:
designated_cities.cpp: In function 'void solve()':
designated_cities.cpp:272:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  272 |     assert(tour.size() == n);
      |            ~~~~~~~~~~~~^~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31064 KB Output is correct
2 Correct 7 ms 37212 KB Output is correct
3 Correct 6 ms 37212 KB Output is correct
4 Correct 6 ms 37464 KB Output is correct
5 Correct 5 ms 37212 KB Output is correct
6 Incorrect 6 ms 37352 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 31068 KB Output is correct
2 Correct 291 ms 57540 KB Output is correct
3 Correct 328 ms 67920 KB Output is correct
4 Correct 275 ms 57436 KB Output is correct
5 Correct 288 ms 58240 KB Output is correct
6 Correct 314 ms 59336 KB Output is correct
7 Correct 239 ms 58248 KB Output is correct
8 Correct 349 ms 68560 KB Output is correct
9 Correct 208 ms 56104 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31064 KB Output is correct
2 Correct 301 ms 57540 KB Output is correct
3 Correct 304 ms 69564 KB Output is correct
4 Correct 265 ms 57432 KB Output is correct
5 Correct 278 ms 58396 KB Output is correct
6 Correct 311 ms 59424 KB Output is correct
7 Correct 233 ms 58700 KB Output is correct
8 Correct 339 ms 64616 KB Output is correct
9 Correct 200 ms 55908 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31064 KB Output is correct
2 Correct 7 ms 37212 KB Output is correct
3 Correct 6 ms 37212 KB Output is correct
4 Correct 6 ms 37464 KB Output is correct
5 Correct 5 ms 37212 KB Output is correct
6 Incorrect 6 ms 37352 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 31068 KB Output is correct
2 Correct 291 ms 57540 KB Output is correct
3 Correct 328 ms 67920 KB Output is correct
4 Correct 275 ms 57436 KB Output is correct
5 Correct 288 ms 58240 KB Output is correct
6 Correct 314 ms 59336 KB Output is correct
7 Correct 239 ms 58248 KB Output is correct
8 Correct 349 ms 68560 KB Output is correct
9 Correct 208 ms 56104 KB Output is correct
10 Correct 5 ms 31064 KB Output is correct
11 Correct 301 ms 57540 KB Output is correct
12 Correct 304 ms 69564 KB Output is correct
13 Correct 265 ms 57432 KB Output is correct
14 Correct 278 ms 58396 KB Output is correct
15 Correct 311 ms 59424 KB Output is correct
16 Correct 233 ms 58700 KB Output is correct
17 Correct 339 ms 64616 KB Output is correct
18 Correct 200 ms 55908 KB Output is correct
19 Correct 5 ms 31068 KB Output is correct
20 Incorrect 302 ms 57584 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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