Submission #1366421

#TimeUsernameProblemLanguageResultExecution timeMemory
1366421thaibaotran555Two Currencies (JOI23_currencies)C++20
100 / 100
746 ms43544 KiB
///TRAN THAI BAO :3

#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

#define maxN 100007
#define oo 1000000000000000000
#define MAXVAL 1000000000

typedef pair<long long, long long> pii;

pii eList[maxN];

vector<pii>station;

int n, p, q;

int up[maxN][20];
long long gold[maxN];

struct QUERY
{
    int lo, hi, mid;
    int s, t, lca;
    long long si;
    int id;
};

bool CMPQUERY(QUERY one, QUERY two)
{
    if(one.mid != two.mid)
        return one.mid < two.mid;
    return one.id < two.id;
}

vector<QUERY>curQ;

struct BIT
{
    long long b1[maxN];
    long long b2[maxN];
    void reset()
    {
        memset(b1, 0, sizeof(b1));
        memset(b2, 0, sizeof(b2));
    }
    void update(long long b[], int pos, long long val)
    {
        while(pos <= n)
        {
            b[pos] += val;
            pos += (pos & -pos);
        }
    }
    long long get(long long b[], int pos)
    {
        long long ans = 0;
        for(; pos > 0; pos -= (pos & -pos))
            ans += b[pos];
        return ans;
    }
    void updRange(int l, int r, long long val)
    {
        update(b1, l, val*(n-l+1));
        update(b1, r+1, -val*(n-r));
        update(b2, l, val);
        update(b2, r+1, -val);
    }
    long long pref(int pos)
    {
        return get(b1, pos) - get(b2, pos)*(n-pos);
    }
    long long range(int l, int r)
    {
        return pref(r) - pref(l-1);
    }
};

vector<int>adj[maxN];
int in[maxN] = {0};
int ou[maxN] = {0};
int h[maxN] = {0};
int curT = 0;

long long ans[maxN];

BIT bit3;
BIT bit1, bit2;

void dfs(int u, int p)
{
    h[u] = h[p]+1;
    up[u][0] = p;
    in[u] = ++curT;
    int v;
    for(int i = 0; i < adj[u].size(); i++)
    {
        v = adj[u][i];
        if(v == p)
            continue;
        dfs(v, u);
    }
    ou[u] = curT;
}

int LCA(int u, int v)
{
    if(h[u] < h[v]) swap(u, v);
    int d = h[u] - h[v];
    for(int i = 0; i < 20; i++)
        if((d >> i) & 1)
            u = up[u][i];
    if(u == v)
        return u;
    for(int i = 19; i >= 0; i--)
        if(up[u][i] != up[v][i])
        {
            u = up[u][i];
            v = up[v][i];
        }
    return up[u][0];
}

void readData()
{
    int u, v, w;
    cin >> n >> p >> q;
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        eList[i] = {u, v};
    }
    dfs(1, 1);
    for(int i = 1; i < 20; i++)
        for(int j = 1; j <= n; j++)
            up[j][i] = up[up[j][i-1]][i-1];
    for(int i = 0; i < p; i++)
    {
        cin >> u >> w;
        v = eList[u].second;
        u = eList[u].first;
        if(up[u][0] != v)
            swap(u, v);
        station.push_back({w, u});
    }
    long long s, t, x, y;
    for(int i = 1; i <= q; i++)
    {
        ans[i] = oo;
        cin >> s >> t >> x >> y;
        gold[i] = x;
        QUERY tmp = {0, p, p/2, s, t, LCA(s, t), y, i};
        curQ.push_back(tmp);
    }
    sort(station.begin(), station.end());
    for(int i = 0; i < station.size(); i++)
    {
        u = station[i].second;
        bit3.updRange(in[u], ou[u], 1);
    }
}

void compute()
{
    int u, v, w;
    vector<QUERY>nxt;
    bit1.reset();
    for(int i = 0; i <= n; i++)
    {
        bit2.b1[i] = bit3.b1[i];
        bit2.b2[i] = bit3.b2[i];
    }
    sort(curQ.begin(), curQ.end(), CMPQUERY);
    int j = 0;
    for(int i = 0; i < curQ.size(); i++)
    {
        QUERY cur = curQ[i];
        while(j < cur.mid)
        {
            w = station[j].first;
            u = station[j].second;
            bit1.updRange(in[u], ou[u], w);
            bit2.updRange(in[u], ou[u], -1);
            j++;
        }
        long long curCost = bit1.range(in[cur.s], in[cur.s]) + bit1.range(in[cur.t], in[cur.t]) - 2ll*bit1.range(in[cur.lca], in[cur.lca]);
        if(curCost <= cur.si)
        {
            long long curAns = bit2.range(in[cur.s], in[cur.s]) + bit2.range(in[cur.t], in[cur.t]) - 2ll*bit2.range(in[cur.lca], in[cur.lca]);
            ans[cur.id] = min(ans[cur.id], curAns);
            cur.lo = cur.mid+1;
            cur.mid = (cur.lo + cur.hi)/2;
        }
        else
        {
            cur.hi = cur.mid-1;
            cur.mid = (cur.lo + cur.hi)/2;
        }
        if(cur.lo <= cur.hi)
            nxt.push_back(cur);
    }
    curQ.clear();
    swap(nxt, curQ);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    readData();
    while(!curQ.empty())
        compute();
    for(int i = 1; i <= q; i++)
        if(ans[i] <= gold[i])
            cout << gold[i] - ans[i] << "\n";
        else cout << "-1\n";
    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void readData()':
currencies.cpp:161:33: warning: narrowing conversion of 's' from 'long long int' to 'int' [-Wnarrowing]
  161 |         QUERY tmp = {0, p, p/2, s, t, LCA(s, t), y, i};
      |                                 ^
currencies.cpp:161:36: warning: narrowing conversion of 't' from 'long long int' to 'int' [-Wnarrowing]
  161 |         QUERY tmp = {0, p, p/2, s, t, LCA(s, t), y, i};
      |                                    ^
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...