답안 #854753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
854753	2023-09-28T18:04:22 Z	boris_mihov	Two Currencies (JOI23_currencies)	C++17	68 / 100	1575 ms	269720 KB

currencies

#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 == n + 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	41 ms	244564 KB	Output is correct
2	Correct	37 ms	244564 KB	Output is correct
3	Correct	36 ms	244560 KB	Output is correct
4	Correct	36 ms	244548 KB	Output is correct
5	Correct	42 ms	248768 KB	Output is correct
6	Correct	45 ms	249168 KB	Output is correct
7	Correct	42 ms	248660 KB	Output is correct
8	Correct	45 ms	248916 KB	Output is correct
9	Correct	47 ms	248916 KB	Output is correct
10	Correct	45 ms	248920 KB	Output is correct
11	Correct	45 ms	248916 KB	Output is correct
12	Correct	52 ms	248924 KB	Output is correct
13	Correct	45 ms	248912 KB	Output is correct
14	Correct	46 ms	248912 KB	Output is correct
15	Correct	46 ms	248916 KB	Output is correct
16	Correct	46 ms	248916 KB	Output is correct
17	Correct	45 ms	248880 KB	Output is correct
18	Correct	45 ms	248916 KB	Output is correct
19	Correct	45 ms	248700 KB	Output is correct
20	Correct	47 ms	248916 KB	Output is correct
21	Correct	45 ms	248924 KB	Output is correct
22	Correct	44 ms	248828 KB	Output is correct
23	Correct	45 ms	248748 KB	Output is correct
24	Correct	46 ms	248916 KB	Output is correct
25	Correct	45 ms	248864 KB	Output is correct
26	Correct	45 ms	248948 KB	Output is correct
27	Correct	42 ms	248916 KB	Output is correct
28	Correct	44 ms	248916 KB	Output is correct
29	Correct	43 ms	248916 KB	Output is correct
30	Correct	45 ms	248940 KB	Output is correct
31	Correct	45 ms	248740 KB	Output is correct
32	Correct	46 ms	248912 KB	Output is correct
33	Correct	46 ms	249172 KB	Output is correct
34	Correct	47 ms	249124 KB	Output is correct
35	Correct	47 ms	249164 KB	Output is correct

Subtask #2
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	244608 KB	Output is correct
2	Correct	45 ms	248912 KB	Output is correct
3	Correct	52 ms	248920 KB	Output is correct
4	Correct	46 ms	248912 KB	Output is correct
5	Correct	556 ms	256672 KB	Output is correct
6	Correct	841 ms	255384 KB	Output is correct
7	Correct	782 ms	255836 KB	Output is correct
8	Correct	634 ms	255928 KB	Output is correct
9	Correct	490 ms	256068 KB	Output is correct
10	Correct	902 ms	256852 KB	Output is correct
11	Correct	986 ms	257056 KB	Output is correct
12	Correct	964 ms	256916 KB	Output is correct
13	Correct	917 ms	257108 KB	Output is correct
14	Correct	892 ms	256952 KB	Output is correct
15	Correct	1556 ms	268620 KB	Output is correct
16	Correct	1575 ms	269184 KB	Output is correct
17	Correct	1478 ms	268016 KB	Output is correct
18	Correct	1169 ms	257108 KB	Output is correct
19	Correct	1079 ms	257372 KB	Output is correct
20	Correct	1134 ms	257228 KB	Output is correct
21	Correct	835 ms	257288 KB	Output is correct
22	Correct	841 ms	257232 KB	Output is correct
23	Correct	850 ms	257268 KB	Output is correct
24	Correct	847 ms	257300 KB	Output is correct
25	Correct	957 ms	256604 KB	Output is correct
26	Correct	939 ms	256732 KB	Output is correct
27	Correct	987 ms	256464 KB	Output is correct
28	Correct	573 ms	256856 KB	Output is correct
29	Correct	538 ms	256936 KB	Output is correct
30	Correct	645 ms	257052 KB	Output is correct
31	Correct	646 ms	256648 KB	Output is correct

Subtask #3
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	244648 KB	Output is correct
2	Correct	45 ms	249168 KB	Output is correct
3	Correct	49 ms	249172 KB	Output is correct
4	Correct	45 ms	249168 KB	Output is correct
5	Correct	792 ms	268396 KB	Output is correct
6	Correct	713 ms	267544 KB	Output is correct
7	Correct	1101 ms	261852 KB	Output is correct
8	Correct	1358 ms	269644 KB	Output is correct
9	Correct	1426 ms	269528 KB	Output is correct
10	Correct	1380 ms	269568 KB	Output is correct
11	Correct	1090 ms	268904 KB	Output is correct
12	Correct	1048 ms	269072 KB	Output is correct
13	Correct	1169 ms	268748 KB	Output is correct
14	Correct	742 ms	269648 KB	Output is correct
15	Correct	705 ms	269588 KB	Output is correct
16	Correct	870 ms	269720 KB	Output is correct
17	Correct	880 ms	269568 KB	Output is correct

Subtask #4
0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	244564 KB	Output is correct
2	Correct	37 ms	244564 KB	Output is correct
3	Correct	36 ms	244560 KB	Output is correct
4	Correct	36 ms	244548 KB	Output is correct
5	Correct	42 ms	248768 KB	Output is correct
6	Correct	45 ms	249168 KB	Output is correct
7	Correct	42 ms	248660 KB	Output is correct
8	Correct	45 ms	248916 KB	Output is correct
9	Correct	47 ms	248916 KB	Output is correct
10	Correct	45 ms	248920 KB	Output is correct
11	Correct	45 ms	248916 KB	Output is correct
12	Correct	52 ms	248924 KB	Output is correct
13	Correct	45 ms	248912 KB	Output is correct
14	Correct	46 ms	248912 KB	Output is correct
15	Correct	46 ms	248916 KB	Output is correct
16	Correct	46 ms	248916 KB	Output is correct
17	Correct	45 ms	248880 KB	Output is correct
18	Correct	45 ms	248916 KB	Output is correct
19	Correct	45 ms	248700 KB	Output is correct
20	Correct	47 ms	248916 KB	Output is correct
21	Correct	45 ms	248924 KB	Output is correct
22	Correct	44 ms	248828 KB	Output is correct
23	Correct	45 ms	248748 KB	Output is correct
24	Correct	46 ms	248916 KB	Output is correct
25	Correct	45 ms	248864 KB	Output is correct
26	Correct	45 ms	248948 KB	Output is correct
27	Correct	42 ms	248916 KB	Output is correct
28	Correct	44 ms	248916 KB	Output is correct
29	Correct	43 ms	248916 KB	Output is correct
30	Correct	45 ms	248940 KB	Output is correct
31	Correct	45 ms	248740 KB	Output is correct
32	Correct	46 ms	248912 KB	Output is correct
33	Correct	46 ms	249172 KB	Output is correct
34	Correct	47 ms	249124 KB	Output is correct
35	Correct	47 ms	249164 KB	Output is correct
36	Correct	36 ms	244608 KB	Output is correct
37	Correct	45 ms	248912 KB	Output is correct
38	Correct	52 ms	248920 KB	Output is correct
39	Correct	46 ms	248912 KB	Output is correct
40	Correct	556 ms	256672 KB	Output is correct
41	Correct	841 ms	255384 KB	Output is correct
42	Correct	782 ms	255836 KB	Output is correct
43	Correct	634 ms	255928 KB	Output is correct
44	Correct	490 ms	256068 KB	Output is correct
45	Correct	902 ms	256852 KB	Output is correct
46	Correct	986 ms	257056 KB	Output is correct
47	Correct	964 ms	256916 KB	Output is correct
48	Correct	917 ms	257108 KB	Output is correct
49	Correct	892 ms	256952 KB	Output is correct
50	Correct	1556 ms	268620 KB	Output is correct
51	Correct	1575 ms	269184 KB	Output is correct
52	Correct	1478 ms	268016 KB	Output is correct
53	Correct	1169 ms	257108 KB	Output is correct
54	Correct	1079 ms	257372 KB	Output is correct
55	Correct	1134 ms	257228 KB	Output is correct
56	Correct	835 ms	257288 KB	Output is correct
57	Correct	841 ms	257232 KB	Output is correct
58	Correct	850 ms	257268 KB	Output is correct
59	Correct	847 ms	257300 KB	Output is correct
60	Correct	957 ms	256604 KB	Output is correct
61	Correct	939 ms	256732 KB	Output is correct
62	Correct	987 ms	256464 KB	Output is correct
63	Correct	573 ms	256856 KB	Output is correct
64	Correct	538 ms	256936 KB	Output is correct
65	Correct	645 ms	257052 KB	Output is correct
66	Correct	646 ms	256648 KB	Output is correct
67	Correct	36 ms	244648 KB	Output is correct
68	Correct	45 ms	249168 KB	Output is correct
69	Correct	49 ms	249172 KB	Output is correct
70	Correct	45 ms	249168 KB	Output is correct
71	Correct	792 ms	268396 KB	Output is correct
72	Correct	713 ms	267544 KB	Output is correct
73	Correct	1101 ms	261852 KB	Output is correct
74	Correct	1358 ms	269644 KB	Output is correct
75	Correct	1426 ms	269528 KB	Output is correct
76	Correct	1380 ms	269568 KB	Output is correct
77	Correct	1090 ms	268904 KB	Output is correct
78	Correct	1048 ms	269072 KB	Output is correct
79	Correct	1169 ms	268748 KB	Output is correct
80	Correct	742 ms	269648 KB	Output is correct
81	Correct	705 ms	269588 KB	Output is correct
82	Correct	870 ms	269720 KB	Output is correct
83	Correct	880 ms	269568 KB	Output is correct
84	Incorrect	642 ms	256104 KB	Output isn't correct
85	Halted	0 ms	0 KB	-

답안 #854753

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 28.0 / 28.0

Subtask #3 30.0 / 30.0

Subtask #4 0 / 32.0

Subtask #1
10.0 / 10.0

Subtask #2
28.0 / 28.0

Subtask #3
30.0 / 30.0

Subtask #4
0 / 32.0