Submission #792556

#	Time	Username	Problem	Language	Result	Execution time	Memory
792556		anhduc2701	Two Currencies (JOI23_currencies)	C++17	100 / 100	1271 ms	128844 KiB

currencies

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 3e5 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, m, q;
vector<int> G[maxn];
struct ask
{
    int s, t, x, y;
} que[maxn];
int p[maxn];
int c[maxn];
struct cp
{
    int p, c;
    bool operator<(const cp &x)
    {
        return c < x.c;
    }
} ch[maxn];
struct BIT
{
    ll bit[maxn];
    void init()
    {
        memset(bit, 0, sizeof(bit));
    }
    void upd(int id, ll val)
    {
        for (id; id <= n; id += id & -id)
        {
            bit[id] += val;
        }
    }
    ll get(int id)
    {
        ll res = 0;
        for (id; id >= 1; id -= id & -id)
        {
            res += bit[id];
        }
        return res;
    }
} A, B;
int tin[maxn];
int tout[maxn];
int s = 0;
int par[maxn];
pair<int, int> rmq[maxn][20];
int eu1[maxn];
int tin1[maxn];
int tout1[maxn];
int s1 = 0;
void dfs(int u, int pa)
{
    tin[u] = ++s;
    tin1[u] = ++s1;
    eu1[s1] = u;
    for (auto v : G[u])
    {
        if (v == pa)
            continue;
        par[v] = u;
        dfs(v, u);
        eu1[++s1] = u;
    }
    tout[u] = s;
}
void init()
{
    for (int i = 1; i <= s1; i++)
    {
        rmq[i][0] = {tin1[eu1[i]], eu1[i]};
    }
    for (int i = 1; (1 << i) <= s1; i++)
    {
        for (int j = 1; j + (1 << i) - 1 <= s1; j++)
        {
            rmq[j][i] = min(rmq[j + (1 << (i - 1))][i - 1], rmq[j][i - 1]);
        }
    }
}
int LCA(int u, int v)
{
    if (tin1[u] > tin1[v])
        swap(u, v);
    int dis = 31 - __builtin_clz(tin1[v] - tin1[u] + 1);
    return min(rmq[tin1[u]][dis], rmq[tin1[v] - (1 << dis) + 1][dis]).se;
}
int l[maxn];
int ans[maxn];
int r[maxn];
pair<int, int> ed[maxn];
vector<int> K[maxn];
void solve()
{
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        ed[i].fi = a;
        ed[i].se = b;
        G[a].pb(b);
        G[b].pb(a);
    }
    dfs(1, -1);
    init();

    for (int i = 1; i <= m; i++)
    {
        cin >> ch[i].p >> ch[i].c;
        if (par[ed[ch[i].p].fi] == ed[ch[i].p].se)
        {
            ch[i].p = ed[ch[i].p].fi;
        }
        else
        {
            ch[i].p = ed[ch[i].p].se;
        }
    }
    sort(ch + 1, ch + 1 + m);
    for (int i = 1; i <= q; i++)
    {
        cin >> que[i].s >> que[i].t >> que[i].x >> que[i].y;
        ans[i] = 1e9;
        l[i] = 0;
        r[i] = m;
    }
    for (int _ = 1; _ <= 18; _++)
    {

        for (int i = 1; i <= q; i++)
        {
            if (l[i] <= r[i])
            {
                int mid = (l[i] + r[i]) >> 1;
                K[mid].pb(i);
            }
        }
        A.init();
        B.init();
        for (int i = 1; i <= m; i++)
        {
            A.upd(tin[ch[i].p], 1);
            A.upd(tout[ch[i].p] + 1, -1);
        }

        for (int i = 0; i <= m; i++)
        {
            if (i)
            {
                B.upd(tin[ch[i].p], ch[i].c);
                B.upd(tout[ch[i].p] + 1, -ch[i].c);
                // cout << tin[ch[i].p] << " " << tout[ch[i].p] << " " << ch[i].c << "\n";
                A.upd(tin[ch[i].p], -1);
                A.upd(tout[ch[i].p] + 1, 1);
            }
            for (auto v : K[i])
            {
                int u = LCA(que[v].s, que[v].t);
                int silver = B.get(tin[que[v].s]) + B.get(tin[que[v].t]) - 2 * B.get(tin[u]);
                // cout << que[v].s << " " << que[v].t << " " << u << "\n";
                int gold = A.get(tin[que[v].s]) + A.get(tin[que[v].t]) - 2 * A.get(tin[u]);
                if (silver <= que[v].y)
                {
                    ans[v] = gold;
                    l[v] = i + 1;
                }
                else
                {
                    r[v] = i - 1;
                }
            }
            K[i].clear();
        }
    }
    for (int i = 1; i <= q; i++)
    {
        if (ans[i] <= que[i].x)
        {
            cout << que[i].x - ans[i] << "\n";
        }
        else
        {
            cout << "-1\n";
        }
    }
}
signed main()
{
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);

    solve();
}

Compilation message (stderr)

currencies.cpp: In member function 'void BIT::upd(long long int, ll)':
currencies.cpp:59:14: warning: statement has no effect [-Wunused-value]
   59 |         for (id; id <= n; id += id & -id)
      |              ^~
currencies.cpp: In member function 'll BIT::get(long long int)':
currencies.cpp:67:14: warning: statement has no effect [-Wunused-value]
   67 |         for (id; id >= 1; id -= id & -id)
      |              ^~

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