Submission #940569

#	Time	Username	Problem	Language	Result	Execution time	Memory
940569		jasen_penchev	Two Currencies (JOI23_currencies)	C++14	100 / 100	1929 ms	150296 KiB

currencies

#include <algorithm>
#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;

/// LCA + Euler tour + Persistent segment tree

const int MAX = 100000;
const int LOG = 17;

struct node
{
    int l, r, gold;
    long long silver;
};

int n, m, q;
int d[MAX + 5];
int root[MAX + 5];
int st[MAX + 5][LOG + 5];
node tree[100 * MAX + 5];
int cnt, in[MAX + 5], out[MAX + 5];
vector< pair<int, int> > G[MAX + 5];
pair<int, int> edges[MAX + 5], checkpoints[MAX + 5];

void DFS(int u, int p)
{
    st[u][0] = p;
    in[u] = ++ cnt;
    for (auto [v, idx] : G[u])
    {
        if (v != p)
        {
            if (edges[idx].first != u) swap(edges[idx].first, edges[idx].second);
            d[v] = d[u] + 1;
            DFS(v, u);
        }
    }
    out[u] = cnt;
}

int build(int l, int r)
{
    int v = ++ cnt;
    if (l == r) return v;

    int mid = (l + r) / 2;
    tree[v].l = build(l, mid);
    tree[v].r = build(mid + 1, r);
    return v;
}

int update(int v, int l, int r, int ql, int qr, int val)
{
    int newv = ++ cnt;
    tree[newv] = tree[v];
    if (ql <= l and r <= qr)
    {
        tree[newv].gold++;
        tree[newv].silver += val;
        return newv;
    }

    int mid = (l + r) / 2;
    if (!(qr < l or mid < ql)) tree[newv].l = update(tree[v].l, l, mid, ql, qr, val);
    if (!(qr < mid + 1 or r < ql)) tree[newv].r = update(tree[v].r, mid + 1, r, ql, qr, val);
    return newv;
}

pair<int, long long> query(int v, int l, int r, int pos)
{
    pair<int, long long> ret = {tree[v].gold, tree[v].silver};
    if (l == r) return ret;

    int mid = (l + r) / 2;
    if (pos <= mid)
    {
        auto [g, s] = query(tree[v].l, l, mid, pos);
        ret.first += g;
        ret.second += s;
    }
    else
    {
        auto [g, s] = query(tree[v].r, mid + 1, r, pos);
        ret.first += g;
        ret.second += s;
    }
    return ret;
}

int LCA(int u, int v)
{
    int du = d[u], dv = d[v];
    if (du > dv)
    {
        swap(u, v);
        swap(du, dv);
    }

    for (int j = LOG; j >= 0; -- j)
    {
        if (dv - (1ll << j) >= du)
        {
            v = st[v][j];
            dv -= (1ll << j);
        }
    }

    for (int j = LOG; j >= 0; -- j)
    {
        if (st[u][j] != st[v][j])
        {
            u = st[u][j];
            v = st[v][j];
        }
    }

    if (u == v) return u;
    return st[u][0];
}

int main()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m >> q;

    for (int i = 1; i < n; ++ i)
    {
        cin >> edges[i].first >> edges[i].second;
        G[edges[i].first].push_back({edges[i].second, i});
        G[edges[i].second].push_back({edges[i].first, i});
    }

    DFS(1, -1);

    for (int j = 1; j <= LOG; ++ j)
    {
        for (int i = 1; i <= n; ++ i)
        {
            st[i][j] = st[st[i][j - 1]][j - 1];
        }
    }

    for (int i = 1; i <= m; ++ i)
    {
        cin >> checkpoints[i].second >> checkpoints[i].first;
        checkpoints[i].second = edges[checkpoints[i].second].second;
    }

    sort(checkpoints + 1, checkpoints + m + 1);

    cnt = 0;
    root[0] = build(1, n);
    for (int i = 1; i <= m; ++ i)
    {
        root[i] = update(root[i - 1], 1, n, in[checkpoints[i].second], out[checkpoints[i].second], checkpoints[i].first);
    }

    for (int i = 1; i <= q; ++ i)
    {
        int s, t, x;
        long long y;
        cin >> s >> t >> x >> y;

        int lca = LCA(s, t);
        int l = 0, r = m + 1, mid;
        while (r - l > 1)
        {
            mid = (l + r) / 2;
            if (query(root[mid], 1, n, in[s]).second + query(root[mid], 1, n, in[t]).second - 2 * query(root[mid], 1, n, in[lca]).second <= y) l = mid;
            else r = mid;
        }

        int ans = x - ((query(root[m], 1, n, in[s]).first + query(root[m], 1, n, in[t]).first - 2 * query(root[m], 1, n, in[lca]).first) -
                       (query(root[l], 1, n, in[s]).first + query(root[l], 1, n, in[t]).first - 2 * query(root[l], 1, n, in[lca]).first));
        if (ans < 0) ans = -1;
        cout << ans << endl;
    }

    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void DFS(int, int)':
currencies.cpp:31:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for (auto [v, idx] : G[u])
      |               ^
currencies.cpp: In function 'std::pair<int, long long int> query(int, int, int, int)':
currencies.cpp:79:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |         auto [g, s] = query(tree[v].l, l, mid, pos);
      |              ^
currencies.cpp:85:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |         auto [g, s] = query(tree[v].r, mid + 1, r, pos);
      |              ^

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