Submission #1108622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108622		jonghak9028	Two Currencies (JOI23_currencies)	C++17	0 / 100	17 ms	24080 KiB

currencies

/* ************************************************************************** */
/*                                                                            */
/*                                                      :::    :::    :::     */
/*   Problem Number: 27992                             :+:    :+:      :+:    */
/*                                                    +:+    +:+        +:+   */
/*   By: js9028 <boj.kr/u/js9028>                    +#+    +#+          +#+  */
/*                                                  +#+      +#+        +#+   */
/*   https://boj.kr/27992                          #+#        #+#      #+#    */
/*   Solved: 2024/11/04 23:42:53 by js9028        ###          ###   ##.kr    */
/*                                                                            */
/* ************************************************************************** */
#include <bits/stdc++.h>
#define fastio (ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL))
using namespace std;

typedef long long ll;
const long long INF = 1e9 + 5;

struct Seg
{
    ll tree[1 << 18];
    int sz = 1 << 17;
    void init()
    {
        memset(tree, 0, sizeof tree);
    }
    void update(int x, ll v)
    {
        x |= sz;
        tree[x] += v;
        while (x >>= 1)
        {
            tree[x] = tree[x << 1] + tree[x << 1 | 1];
        }
    }

    ll query(int l, int r)
    {
        l |= sz, r |= sz;
        int ret = 0;
        while (l <= r)
        {
            if (l & 1)
                ret += tree[l++];
            if (~r & 1)
                ret += tree[r--];
            l >>= 1, r >>= 1;
        }
        return ret;
    }
};

class HLD
{
public:
    int sz[101010] = {0}, dep[101010] = {0}, par[101010] = {0}, top[101010] = {0}, in[101010] = {0}, out[101010] = {0};
    vector<int> g[101010];
    vector<int> inp[101010]; // 입력 / 양방향 그래프
    Seg seg;
    int chk[101010] = {0};
    void dfs(int v = 1)
    {
        chk[v] = 1;
        for (auto i : inp[v])
        {
            if (chk[i])
                continue;
            chk[i] = 1;
            g[v].push_back(i);
            dfs(i);
        }
    }

    void dfs1(int v = 1)
    {
        sz[v] = 1;
        for (auto &i : g[v])
        {
            dep[i] = dep[v] + 1;
            par[i] = v;
            dfs1(i);
            sz[v] += sz[i];
            if (sz[i] > sz[g[v][0]])
                swap(i, g[v][0]);
        }
    }

    int pv = 0;
    void dfs2(int v = 1)
    {
        in[v] = ++pv;
        for (auto i : g[v])
        {
            top[i] = i == g[v][0] ? top[v] : i;
            dfs2(i);
        }
        out[v] = pv;
    }

    void update(int v, int w)
    {
        seg.update(in[v], w);
    }

    ll query(int a, int b)
    {
        ll ret = 0;
        while (top[a] ^ top[b])
        {
            if (dep[top[a]] < dep[top[b]])
                swap(a, b);
            int st = top[a];
            ret += seg.query(in[st], in[a]);
            a = par[st];
        }
        if (dep[a] > dep[b])
            swap(a, b);
        ret += seg.query(in[a] + 1, in[b]);
        return ret;
    }
};
int n, m, q;
HLD hld, chld;
pair<int, int> edge[101011];
vector<pair<int, int>> upe;
ll X[101011], Y[101011];
ll ans[101011];
int A[101011], B[101011];
int cnt[101011];

int main()
{
    fastio;
    cin >> n >> m >> q;
    for (int i = 1; i <= n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        hld.inp[a].push_back(b);
        hld.inp[b].push_back(a);
        chld.inp[a].push_back(b);
        chld.inp[b].push_back(a);
        edge[i] = {a, b};
    }
    hld.dfs();
    hld.dfs1();
    hld.dfs2();
    chld.dfs();
    chld.dfs1();
    chld.dfs2();
    for (int i = 1; i <= n - 1; i++)
    {
        auto &p = edge[i];
        if (hld.dep[p.first] < hld.dep[p.second])
            swap(p.first, p.second);
    }
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        upe.push_back({b, a});
        chld.update(edge[a].first, 1);
    }

    sort(upe.begin(), upe.end());
    for (int i = 0; i < q; i++)
    {
        cin >> A[i] >> B[i] >> X[i] >> Y[i];
        cnt[i] = chld.query(A[i], B[i]);
    }
    vector<pair<int, int>> v(q, {0, m});
    memset(ans, -1, sizeof ans);
    while (1)
    {
        bool f = 1;
        vector<int> pb[m + 1];
        for (int i = 0; i < q; i++)
        {
            auto &p = v[i];
            if (p.first <= p.second)
            {
                pb[(p.first + p.second) / 2].push_back(i);
                f = 0;
            }
        }

        if (f)
            break;
        hld.seg.init();
        chld.seg.init();
        for (int i = 0; i <= m; i++)
        {
            for (int j : pb[i])
            {
                ll tot = hld.query(A[j], B[j]);
                ll nt = chld.query(A[j], B[j]);
                if (tot <= Y[j])
                {
                    ans[j] = X[j] - max(0ll, (cnt[j] - nt));
                    v[j].first = i + 1;
                }
                else
                {
                    v[j].second = i - 1;
                }
            }
            if (i == m)
                continue;
            hld.update(edge[upe[i].second].first, upe[i].first);
            chld.update(edge[upe[i].second].first, 1);
        }
    }
    for (int i = 0; i < q; i++)
    {
        cout << (ans[i] < 0 ? -1 : ans[i]) << "\n";
    }

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32