Submission #1086562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086562		Thanhs	Two Currencies (JOI23_currencies)	C++14	100 / 100	963 ms	52240 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define double long double
 
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define fi first
#define se second
#define aint(x) x.begin(), x.end()
 
// mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
// int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 1e5 + 5;
const int LG = 18;

vector<int> g[NM];
vector<pair<int, int>> cost;
int n, m, q, lw[NM], ans[NM], tin[NM], up[NM][LG], timer, tout[NM], dep[NM];
pair<int, int> e[NM];

struct BIT
{
    int dt[NM];
    void reset()
    {
        memset(dt, 0, sizeof dt);
    }
    void upd(int i, int v)
    {
        for (; i <= n; i += i & -i)
            dt[i] += v;
    }
    void upd(int l, int r, int v)
    {
        upd(l, v);
        upd(r + 1, -v);
    }
    int get(int i)
    {
        int ans = 0;
        for (; i; i -= i & -i)
            ans += dt[i];
        return ans;
    }
}bit[4];

struct Query
{
    int s, t, x, y, l, r, id, m, lca;
    Query(int _s, int _t, int _x, int _y, int _l, int _r, int _id, int _lca) : s(_s), t(_t), x(_x), y(_y), l(_l), r(_r), id(_id), lca(_lca) {}
};

vector<Query> Q;

void dfs(int u)
{
    for (int i = 1; up[u][i - 1]; i++)
        up[u][i] = up[up[u][i - 1]][i - 1];
    tin[u] = ++timer;
    for (int v : g[u])
        if (!tin[v])
        {
            dep[v] = dep[u] + 1;
            up[v][0] = u;
            dfs(v);
        }
    tout[u] = timer;
}

int lca(int u, int v)
{
    while (dep[u] != dep[v])
    {
        if (dep[u] < dep[v])
            swap(u, v);
        int t = dep[u] - dep[v];
        for (; t; t ^= t & -t)
            u = up[u][__lg(t & -t)];
    }
    if (u == v)
        return u;
    for (int i = LG - 1; i >= 0; i--)
        if (up[u][i] != up[v][i])
        {
            u = up[u][i];
            v = up[v][i];
        }
    return up[u][0];
}

int myfloor(int x, int y)
{
    return x / y;
}

void solve()
{
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        e[i] = {u, v};
    }
    dfs(1);
    for (int i = 1; i < n; i++)
        lw[i] = (tin[e[i].fi] > tin[e[i].se] ? e[i].fi : e[i].se);
    while (m--)
    {
        int p, c;
        cin >> p >> c;
        cost.emplace_back(c, lw[p]);
    }   
    sort(cost.begin(), cost.end());
    for (int i = 1; i <= q; i++)
    {
        int s, t, x, y;
        cin >> s >> t >> x >> y;
        Q.emplace_back(tin[s], tin[t], x, y, 0, 1e9 + 1, i - 1, tin[lca(s, t)]);
    }
    while (1)
    {
        bit[0].reset();
        bit[1].reset();
        bool changed = 0;
        vector<pair<int, int>> wait;
        for (auto &query : Q)
            if (query.l < query.r - 1)
            {
                changed = 1;
                query.m = query.l + query.r >> 1;
                wait.emplace_back(query.m, query.id);
            }
        sort(wait.begin(), wait.end());
        int ptrl = 0, ptrr = 0;
        for (auto query : wait)
        {
            while (ptrr < cost.size() && cost[ptrr].fi <= query.fi)
            {
                bit[0].upd(tin[cost[ptrr].se], tout[cost[ptrr].se], 1);
                bit[1].upd(tin[cost[ptrr].se], tout[cost[ptrr].se], cost[ptrr].fi);
                ptrr++;
            }
            while (ptrl < ptrr && cost[ptrl].fi < query.fi)
            {
                bit[0].upd(tin[cost[ptrl].se], tout[cost[ptrl].se], -1);
                ptrl++;
            }
            Query &x = Q[query.se];
            int path = bit[1].get(x.s) + bit[1].get(x.t) - 2 * bit[1].get(x.lca);
            int cnt = bit[0].get(x.s) + bit[0].get(x.t) - 2 * bit[0].get(x.lca);
            if (path - max(0ll, cnt - 1) * query.fi <= x.y)
                x.l = x.m;
            else
                x.r = x.m;
        }
        if (!changed)
            break;
    }
    // for (int i = 0; i < q; i++)
    //     cout << Q[i].l << ' ' << Q[i].r << ' ' << Q[i].m << endl;
    vector<pair<int, int>> wait;
    for (auto &query : Q)
        wait.emplace_back(query.l, query.id);
    sort(wait.begin(), wait.end());
    int ptrl = 0, ptrr = 0;
    bit[0].reset();
    bit[1].reset();
    for (auto t : cost)
        bit[2].upd(tin[t.se], tout[t.se], 1);
    for (auto query : wait)
    {
        while (ptrr < cost.size() && cost[ptrr].fi <= query.fi)
        {
            bit[0].upd(tin[cost[ptrr].se], tout[cost[ptrr].se], 1);
            bit[1].upd(tin[cost[ptrr].se], tout[cost[ptrr].se], cost[ptrr].fi);
            bit[3].upd(tin[cost[ptrr].se], tout[cost[ptrr].se], 1);
            ptrr++;
        }
        while (ptrl < ptrr && cost[ptrl].fi < query.fi)
        {
            bit[0].upd(tin[cost[ptrl].se], tout[cost[ptrl].se], -1);
            ptrl++;
        }
        Query &x = Q[query.se];
        int path = bit[1].get(x.s) + bit[1].get(x.t) - 2 * bit[1].get(x.lca);
        int cnt = bit[0].get(x.s) + bit[0].get(x.t) - 2 * bit[0].get(x.lca);
        int cntt = min(cnt, myfloor(x.y - path + cnt * query.fi, query.fi));
        // cout << x.y - path << endl;
        int lmao = bit[2].get(x.s) + bit[2].get(x.t) - 2 * bit[2].get(x.lca);
        int Lmao = bit[3].get(x.s) + bit[3].get(x.t) - 2 * bit[3].get(x.lca);
        ans[x.id + 1] = x.x - (lmao - (Lmao - cnt + cntt));
    }
    for (int i = 1; i <= q; i++)
        cout << (ans[i] < 0 ? -1 : ans[i]) << endl;
}

signed main()
{
    fastIO
    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    int tc = 1; // cin >> tc;
    while (tc--)
        solve();

}

Compilation message (stderr)

currencies.cpp: In function 'void solve()':
currencies.cpp:138:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  138 |                 query.m = query.l + query.r >> 1;
      |                           ~~~~~~~~^~~~~~~~~
currencies.cpp:145:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |             while (ptrr < cost.size() && cost[ptrr].fi <= query.fi)
      |                    ~~~~~^~~~~~~~~~~~~
currencies.cpp:180:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |         while (ptrr < cost.size() && cost[ptrr].fi <= query.fi)
      |                ~~~~~^~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:210:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  210 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:211:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  211 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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