Submission #1261986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261986		Zbyszek99	Two Currencies (JOI23_currencies)	C++20	68 / 100	5080 ms	700992 KiB

currencies

#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<<30)-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(ll x, node* prev)
    {
        sum = prev -> sum + x;
        cnt = prev -> cnt + 1;
        if(l == r) return;
        prev -> sons();
        if(x <= (l+r)/2)
        {
            right = prev->right;
            left = new node;
            left -> l = l;
            left -> r = (l+r)/2;
            left->add(x,prev->left);
        }
        else
        {
            left = prev->left;
            right = new node;
            right -> l = (l+r)/2+1;
            right -> r = r;
            right -> add(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;

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,&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;
    }
    rep(i,m)
    {
        int a,b;
        cin >> a >> b;
        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 = 1e9;
        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)/(ans3+1));
        ans = depth[a]+depth[b]-2*depth[lca]-ans;
        if(ans <= x) cout << x-ans << "\n";
        else cout << "-1\n";
    }
}

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