oj.uz

답안 #854754

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
854754 2023-09-28T18:06:33 Z boris_mihov Two Currencies (JOI23_currencies) C++17
100 / 100
 1494 ms 269792 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXLOG = 100;
const int INF  = 1e9;

int n, m, q;
struct PersistentSegmentTree
{
    struct Node
    {
        llong sum;
        int active;
        int l, r;

        Node()
        {
            sum = l = r = active = 0;
        }
    };

    int cnt;
    Node tree[MAXN * MAXLOG];
    void build(int l, int r, int node)
    {
        if (l == r)
        {
            tree[node].sum = 0;
            tree[node].active = 0;
            return;
        }

        int mid = (l + r) / 2;
        tree[node].l = cnt++;
        tree[node].r = cnt++;

        build(l, mid, tree[node].l);
        build(mid + 1, r, tree[node].r);
        tree[node].sum = 0;
        tree[node].active = 0;
    }

    void update(int l, int r, int node, int oldNode, int queryPos, int queryVal)
    {
        tree[node].l = tree[oldNode].l;
        tree[node].r = tree[oldNode].r;
        tree[node].sum = tree[oldNode].sum;
        tree[node].active = tree[oldNode].active;

        if (l == r)
        {
            tree[node].sum = queryVal;
            tree[node].active = 1;
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid)
        {
            tree[node].l = ++cnt; 
            update(l, mid, tree[node].l, tree[oldNode].l, queryPos, queryVal);
        } else
        {
            tree[node].r = ++cnt; 
            update(mid + 1, r, tree[node].r, tree[oldNode].r, queryPos, queryVal);
        }

        tree[node].sum = tree[tree[node].l].sum + tree[tree[node].r].sum;
        tree[node].active = tree[tree[node].l].active + tree[tree[node].r].active;
    }

    llong query(int l, int r, int node, int queryL, int queryR)
    {
        if (node == 0)
        {
            return 0;
        }

        if (queryL <= l && r <= queryR)
        {
            return tree[node].sum;
        }

        llong sum = 0;        
        int mid = (l + r) / 2;
        if (queryL <= mid)
        {
            sum += query(l, mid, tree[node].l, queryL, queryR);
        }

        if (mid + 1 <= queryR)
        {
            sum += query(mid + 1, r, tree[node].r, queryL, queryR);
        }

        return sum;
    }

    int queryActive(int l, int r, int node, int queryL, int queryR)
    {
        if (node == 0)
        {
            return 0;
        }

        if (queryL <= l && r <= queryR)
        {
            return tree[node].active;
        }

        int sum = 0;        
        int mid = (l + r) / 2;
        if (queryL <= mid)
        {
            sum += queryActive(l, mid, tree[node].l, queryL, queryR);
        }

        if (mid + 1 <= queryR)
        {
            sum += queryActive(mid + 1, r, tree[node].r, queryL, queryR);
        }

        return sum;
    }

    void build()
    {
        cnt = 1;
        build(1, m, 1);
    }

    int update(int idx, int pos, int val)
    {
        int root = ++cnt;
        update(1, m, root, idx, pos, val);
        return root;
    }

    llong query(int idx, int l, int r)
    {
        return query(1, m, idx, l, r);
    }

    int queryActive(int idx, int l, int r)
    {
        return queryActive(1, m, idx, l, r);
    }
};

struct SparseLCA
{
    int sparse[MAXLOG][MAXN];
    int dep[MAXN];

    void build(int par[], int d[])
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            sparse[0][i] = par[i];
            dep[i] = d[i];
        }

        for (int lg = 1 ; (1 << lg) <= n ; ++lg)
        {
            for (int i = 1 ; i <= n ; ++i)
            {
                sparse[lg][i] = sparse[lg - 1][sparse[lg - 1][i]];
            }
        }
    }

    int equalize(int u, int v)
    {
        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (dep[sparse[log][u]] >= dep[v])
            {
                u = sparse[log][u];
            }
        }

        return u;
    }

    int calcLCA(int u, int v)
    {
        if (u == v)
        {
            return u;
        }

        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (sparse[log][u] != sparse[log][v])
            {
                u = sparse[log][u];
                v = sparse[log][v];
            }
        }

        return sparse[0][u];
    }

    int findLCA(int u, int v)
    {
        if (dep[u] < dep[v])
        {
            std::swap(u, v);
        }

        return calcLCA(equalize(u, v), v);
    }
};

SparseLCA sparse;
PersistentSegmentTree tree;
std::vector <int> g[MAXN];
std::vector <int> edgesToAdd[MAXN];
int from[MAXN];
int to[MAXN];
int p[MAXN];
int c[MAXN];
int perm[MAXN];
int inPerm[MAXN];
int idx[MAXN];
int par[MAXN];
int dep[MAXN];

void dfs(int node, int p)
{
    par[node] = p;
    dep[node] = dep[p] + 1;

    for (const int &u : g[node])
    {
        if (u == p)
        {
            continue;
        }

        dfs(u, node);
    }
}

void dfsBuild(int node, int parIdx)
{
    idx[node] = parIdx;
    for (const int &i : edgesToAdd[node])
    {
        idx[node] = tree.update(idx[node], inPerm[i], c[i]);
    }

    for (const int &u : g[node])
    {
        if (u == par[node])
        {
            continue;
        }

        dfsBuild(u, idx[node]);
    }
}

void solve()
{
    dfs(1, 0);
    sparse.build(par, dep);
    tree.build();

    std::iota(perm + 1, perm + 1 + m, 1);
    std::sort(perm + 1, perm + 1 + m, [&](int x, int y)
    {
        return c[x] < c[y];
    });

    for (int i = 1 ; i <= m ; ++i)
    {
        inPerm[perm[i]] = i;
    }

    for (int i = 1 ; i < n ; ++i)
    {
        if (from[i] == par[to[i]])
        {
            std::swap(from[i], to[i]);
        }
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        edgesToAdd[from[p[i]]].push_back(i);
    }

    dfsBuild(1, 1);
    for (int i = 1 ; i <= q ; ++i)
    {
        int x, y, gold, lca;
        llong silver;

        std::cin >> x >> y >> gold >> silver;
        lca = sparse.findLCA(x, y);

        int l = 0, r = m + 1, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (tree.query(idx[x], 1, mid) + tree.query(idx[y], 1, mid) - 2 * tree.query(idx[lca], 1, mid) <= silver) l = mid;
            else r = mid;
        } 

        if (r == m + 1)
        {
            std::cout << gold << '\n';
        } else
        {
            int curr = tree.queryActive(idx[x], r, m) + tree.queryActive(idx[y], r, m) - 2 * tree.queryActive(idx[lca], r, m);
            if (gold < curr) std::cout << -1 << '\n';
            else std::cout << gold - curr << '\n';
        }
    }
}  

void input()
{
    std::cin >> n >> m >> q;
    for (int i = 1 ; i < n ; ++i)
    {
        std::cin >> from[i] >> to[i];
        g[from[i]].push_back(to[i]);
        g[to[i]].push_back(from[i]);
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        std::cin >> p[i] >> c[i];
    }
}

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

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

    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 244564 KB Output is correct
2 Correct 36 ms 244564 KB Output is correct
3 Correct 38 ms 244464 KB Output is correct
4 Correct 37 ms 244568 KB Output is correct
5 Correct 44 ms 248912 KB Output is correct
6 Correct 46 ms 248912 KB Output is correct
7 Correct 43 ms 248660 KB Output is correct
8 Correct 45 ms 248916 KB Output is correct
9 Correct 46 ms 248688 KB Output is correct
10 Correct 45 ms 248700 KB Output is correct
11 Correct 46 ms 248912 KB Output is correct
12 Correct 46 ms 249068 KB Output is correct
13 Correct 46 ms 248912 KB Output is correct
14 Correct 46 ms 248912 KB Output is correct
15 Correct 46 ms 249004 KB Output is correct
16 Correct 45 ms 248912 KB Output is correct
17 Correct 46 ms 248860 KB Output is correct
18 Correct 45 ms 249248 KB Output is correct
19 Correct 44 ms 248916 KB Output is correct
20 Correct 44 ms 248924 KB Output is correct
21 Correct 44 ms 248916 KB Output is correct
22 Correct 47 ms 248984 KB Output is correct
23 Correct 46 ms 248872 KB Output is correct
24 Correct 45 ms 248920 KB Output is correct
25 Correct 45 ms 249168 KB Output is correct
26 Correct 43 ms 248912 KB Output is correct
27 Correct 43 ms 248916 KB Output is correct
28 Correct 43 ms 248916 KB Output is correct
29 Correct 42 ms 248916 KB Output is correct
30 Correct 49 ms 248916 KB Output is correct
31 Correct 47 ms 248920 KB Output is correct
32 Correct 45 ms 248912 KB Output is correct
33 Correct 44 ms 249144 KB Output is correct
34 Correct 45 ms 249180 KB Output is correct
35 Correct 44 ms 249172 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 244564 KB Output is correct
2 Correct 44 ms 248912 KB Output is correct
3 Correct 44 ms 248916 KB Output is correct
4 Correct 44 ms 248916 KB Output is correct
5 Correct 566 ms 256864 KB Output is correct
6 Correct 816 ms 255592 KB Output is correct
7 Correct 718 ms 255860 KB Output is correct
8 Correct 547 ms 255672 KB Output is correct
9 Correct 482 ms 255852 KB Output is correct
10 Correct 906 ms 256876 KB Output is correct
11 Correct 914 ms 256888 KB Output is correct
12 Correct 933 ms 257124 KB Output is correct
13 Correct 897 ms 256936 KB Output is correct
14 Correct 912 ms 256852 KB Output is correct
15 Correct 1404 ms 268456 KB Output is correct
16 Correct 1408 ms 269284 KB Output is correct
17 Correct 1437 ms 267960 KB Output is correct
18 Correct 1116 ms 257140 KB Output is correct
19 Correct 1088 ms 256980 KB Output is correct
20 Correct 1094 ms 257104 KB Output is correct
21 Correct 807 ms 257480 KB Output is correct
22 Correct 806 ms 257340 KB Output is correct
23 Correct 827 ms 257328 KB Output is correct
24 Correct 815 ms 257320 KB Output is correct
25 Correct 923 ms 256720 KB Output is correct
26 Correct 885 ms 256608 KB Output is correct
27 Correct 973 ms 256716 KB Output is correct
28 Correct 572 ms 257364 KB Output is correct
29 Correct 539 ms 256784 KB Output is correct
30 Correct 629 ms 256872 KB Output is correct
31 Correct 647 ms 257116 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 244560 KB Output is correct
2 Correct 45 ms 249168 KB Output is correct
3 Correct 45 ms 249168 KB Output is correct
4 Correct 47 ms 249176 KB Output is correct
5 Correct 781 ms 268156 KB Output is correct
6 Correct 720 ms 267344 KB Output is correct
7 Correct 1078 ms 261424 KB Output is correct
8 Correct 1393 ms 269388 KB Output is correct
9 Correct 1375 ms 269612 KB Output is correct
10 Correct 1370 ms 269672 KB Output is correct
11 Correct 1064 ms 268984 KB Output is correct
12 Correct 1077 ms 268840 KB Output is correct
13 Correct 1082 ms 268932 KB Output is correct
14 Correct 720 ms 269792 KB Output is correct
15 Correct 713 ms 269260 KB Output is correct
16 Correct 849 ms 269396 KB Output is correct
17 Correct 831 ms 269532 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 244564 KB Output is correct
2 Correct 36 ms 244564 KB Output is correct
3 Correct 38 ms 244464 KB Output is correct
4 Correct 37 ms 244568 KB Output is correct
5 Correct 44 ms 248912 KB Output is correct
6 Correct 46 ms 248912 KB Output is correct
7 Correct 43 ms 248660 KB Output is correct
8 Correct 45 ms 248916 KB Output is correct
9 Correct 46 ms 248688 KB Output is correct
10 Correct 45 ms 248700 KB Output is correct
11 Correct 46 ms 248912 KB Output is correct
12 Correct 46 ms 249068 KB Output is correct
13 Correct 46 ms 248912 KB Output is correct
14 Correct 46 ms 248912 KB Output is correct
15 Correct 46 ms 249004 KB Output is correct
16 Correct 45 ms 248912 KB Output is correct
17 Correct 46 ms 248860 KB Output is correct
18 Correct 45 ms 249248 KB Output is correct
19 Correct 44 ms 248916 KB Output is correct
20 Correct 44 ms 248924 KB Output is correct
21 Correct 44 ms 248916 KB Output is correct
22 Correct 47 ms 248984 KB Output is correct
23 Correct 46 ms 248872 KB Output is correct
24 Correct 45 ms 248920 KB Output is correct
25 Correct 45 ms 249168 KB Output is correct
26 Correct 43 ms 248912 KB Output is correct
27 Correct 43 ms 248916 KB Output is correct
28 Correct 43 ms 248916 KB Output is correct
29 Correct 42 ms 248916 KB Output is correct
30 Correct 49 ms 248916 KB Output is correct
31 Correct 47 ms 248920 KB Output is correct
32 Correct 45 ms 248912 KB Output is correct
33 Correct 44 ms 249144 KB Output is correct
34 Correct 45 ms 249180 KB Output is correct
35 Correct 44 ms 249172 KB Output is correct
36 Correct 35 ms 244564 KB Output is correct
37 Correct 44 ms 248912 KB Output is correct
38 Correct 44 ms 248916 KB Output is correct
39 Correct 44 ms 248916 KB Output is correct
40 Correct 566 ms 256864 KB Output is correct
41 Correct 816 ms 255592 KB Output is correct
42 Correct 718 ms 255860 KB Output is correct
43 Correct 547 ms 255672 KB Output is correct
44 Correct 482 ms 255852 KB Output is correct
45 Correct 906 ms 256876 KB Output is correct
46 Correct 914 ms 256888 KB Output is correct
47 Correct 933 ms 257124 KB Output is correct
48 Correct 897 ms 256936 KB Output is correct
49 Correct 912 ms 256852 KB Output is correct
50 Correct 1404 ms 268456 KB Output is correct
51 Correct 1408 ms 269284 KB Output is correct
52 Correct 1437 ms 267960 KB Output is correct
53 Correct 1116 ms 257140 KB Output is correct
54 Correct 1088 ms 256980 KB Output is correct
55 Correct 1094 ms 257104 KB Output is correct
56 Correct 807 ms 257480 KB Output is correct
57 Correct 806 ms 257340 KB Output is correct
58 Correct 827 ms 257328 KB Output is correct
59 Correct 815 ms 257320 KB Output is correct
60 Correct 923 ms 256720 KB Output is correct
61 Correct 885 ms 256608 KB Output is correct
62 Correct 973 ms 256716 KB Output is correct
63 Correct 572 ms 257364 KB Output is correct
64 Correct 539 ms 256784 KB Output is correct
65 Correct 629 ms 256872 KB Output is correct
66 Correct 647 ms 257116 KB Output is correct
67 Correct 36 ms 244560 KB Output is correct
68 Correct 45 ms 249168 KB Output is correct
69 Correct 45 ms 249168 KB Output is correct
70 Correct 47 ms 249176 KB Output is correct
71 Correct 781 ms 268156 KB Output is correct
72 Correct 720 ms 267344 KB Output is correct
73 Correct 1078 ms 261424 KB Output is correct
74 Correct 1393 ms 269388 KB Output is correct
75 Correct 1375 ms 269612 KB Output is correct
76 Correct 1370 ms 269672 KB Output is correct
77 Correct 1064 ms 268984 KB Output is correct
78 Correct 1077 ms 268840 KB Output is correct
79 Correct 1082 ms 268932 KB Output is correct
80 Correct 720 ms 269792 KB Output is correct
81 Correct 713 ms 269260 KB Output is correct
82 Correct 849 ms 269396 KB Output is correct
83 Correct 831 ms 269532 KB Output is correct
84 Correct 597 ms 256044 KB Output is correct
85 Correct 628 ms 254732 KB Output is correct
86 Correct 587 ms 254696 KB Output is correct
87 Correct 1004 ms 256988 KB Output is correct
88 Correct 924 ms 256852 KB Output is correct
89 Correct 925 ms 256760 KB Output is correct
90 Correct 934 ms 256980 KB Output is correct
91 Correct 906 ms 256848 KB Output is correct
92 Correct 1455 ms 265112 KB Output is correct
93 Correct 1494 ms 267400 KB Output is correct
94 Correct 1120 ms 257620 KB Output is correct
95 Correct 1119 ms 257424 KB Output is correct
96 Correct 1120 ms 257108 KB Output is correct
97 Correct 1125 ms 257088 KB Output is correct
98 Correct 802 ms 257080 KB Output is correct
99 Correct 844 ms 257224 KB Output is correct
100 Correct 838 ms 256928 KB Output is correct
101 Correct 813 ms 256968 KB Output is correct
102 Correct 953 ms 256280 KB Output is correct
103 Correct 942 ms 256280 KB Output is correct
104 Correct 899 ms 256432 KB Output is correct
105 Correct 607 ms 256896 KB Output is correct
106 Correct 563 ms 257108 KB Output is correct
107 Correct 605 ms 256964 KB Output is correct
108 Correct 599 ms 256852 KB Output is correct