Submission #1261992

#TimeUsernameProblemLanguageResultExecution timeMemory
1261992Zbyszek99Two Currencies (JOI23_currencies)C++20
100 / 100
2132 ms157996 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

struct node
{
    int l = 0;
    int r = (1<<18)-1;
    ll sum = 0;
    int cnt = 0;
    node* left = NULL;
    node* right = NULL;
    void sons()
    {
        if(left == NULL)
        {
            left = new node;
            left -> l = l;
            left -> r = (l+r)/2;
            right = new node;
            right -> l = (l+r)/2+1;
            right -> r = r;
        }
    }
    void add(int p, ll x, node* prev)
    {
        sum = prev -> sum + x;
        cnt = prev -> cnt + 1;
        if(l == r) return;
        prev -> sons();
        if(p <= (l+r)/2)
        {
            right = prev->right;
            left = new node;
            left -> l = l;
            left -> r = (l+r)/2;
            left->add(p,x,prev->left);
        }
        else
        {
            left = prev->left;
            right = new node;
            right -> l = (l+r)/2+1;
            right -> r = r;
            right -> add(p,x,prev->right);
        }
    }
    pll query(int l2, int r2)
    {
        if(l >= l2 && r <= r2) return {sum,cnt};
        if(r < l2 || l > r2) return {0,0};
        sons();
        pll a = left->query(l2,r2);
        pll b = right->query(l2,r2);
        return {a.ff+b.ff,a.ss+b.ss};
    }
};

vi graph[100001];
vector<pll> cost[100001];
int pre[100001];
int maxpre[100001];
int tree_ind[100001];
int depth[100001];
int jump[100001][18];
pii ends_edge[100001];
int cur_pre = 0;
vector<node> nodes;
map<int,ll> rel_val;
map<int,int> ind;

void dfs(int v, int pop, int prev_tree)
{
    int cnt = 0;
    forall(it,cost[v])
    {
        if(it.ff != pop) continue;
        cnt++;
        node* xd = new node;
        xd->add(it.ss,rel_val[it.ss],&nodes[prev_tree]);
        nodes.pb(*xd);
        prev_tree = siz(nodes)-1;
    }
    jump[v][0] = pop;
    tree_ind[v] = prev_tree;
    pre[v] = cur_pre++;
    depth[v] = depth[pop]+cnt;
    maxpre[v] = pre[v];
    forall(it,graph[v])
    {
        if(it != pop)
        {
            dfs(it,v,prev_tree);
            maxpre[v] = maxpre[it];
        }
    }
}

int lcaf(int a, int b)
{
    if(pre[b] >= pre[a] && pre[b] <= maxpre[a]) return a;
    for(int bit = 17; bit >= 0; bit--)
    {
        int l2 = jump[a][bit];
        if(!(pre[b] >= pre[l2] && pre[b] <= maxpre[l2])) a = l2;
    }
    return jump[a][0];
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n,m,q;
    cin >> n >> m >> q;
    rep(i,n-1)
    {
        int a,b;
        cin >> a >> b;
        graph[a].pb(b);
        graph[b].pb(a);
        ends_edge[i+1].ff = a;
        ends_edge[i+1].ss = b;
    }
    vector<pii> pom;
    rel_val[0] = 1;
    rep(i,m)
    {
        int a,b;
        cin >> a >> b;
        rel_val[b] = 1;
        pom.pb({a,b});
    }
    int cur = 0;
    forall(it,rel_val)
    {
        rel_val[cur] = it.ff;
        ind[it.ff] = cur++;
    }
    rel_val[cur] = 1e16;
    forall(it,pom)
    {
        int a = it.ff;
        int b = ind[it.ss];
        cost[ends_edge[a].ff].pb({ends_edge[a].ss,b});
        cost[ends_edge[a].ss].pb({ends_edge[a].ff,b});
    }
    node xd;
    nodes.pb(xd);
    dfs(1,0,0);
    pre[0] = -1;
    maxpre[0] = n+1;
    rep2(bit,1,17)
    {
        rep2(i,1,n)
        {
            jump[i][bit] = jump[jump[i][bit-1]][bit-1];
        }
    }
    rep(qq,q)
    {
        int a,b,x;
        ll y;
        cin >> a >> b >> x >> y;
        int lca = lcaf(a,b);
        int l = 0;
        int r = cur-1;
        int ans = 0;
        ll ans2 = 0;
        ll ans3 = 0;
        while(l <= r)
        {
            int mid = (l+r)/2;
            pll p1 = nodes[tree_ind[a]].query(0,mid);
            pll p2 = nodes[tree_ind[b]].query(0,mid);
            pll p3 = nodes[tree_ind[lca]].query(0,mid);
            ll sum = p1.ff+p2.ff-2*p3.ff;
            if(sum <= y)
            {
                ans = p1.ss+p2.ss-2*p3.ss;
                ans2 = sum;
                ans3 = mid;
                l = mid+1;
            }
            else
            {
                r = mid-1;
            }
        }
        pll p1 = nodes[tree_ind[a]].query(ans3+1,ans3+1);
        pll p2 = nodes[tree_ind[b]].query(ans3+1,ans3+1);
        pll p3 = nodes[tree_ind[lca]].query(ans3+1,ans3+1);
        ans += min(p1.ss+p2.ss-2*p3.ss,(y-ans2)/rel_val[ans3+1]);
        ans = depth[a]+depth[b]-2*depth[lca]-ans;
        if(ans <= x) cout << x-ans << "\n";
        else cout << "-1\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...