Submission #1308085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308085		thnhann	Two Currencies (JOI23_currencies)	C++20	100 / 100	1814 ms	63580 KiB

currencies

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define ill pair<ll,ll>
#define el cout<<'\n'
#define int long long

const ll mod=1e9+7;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
const int nmax=1e5;
const int inf =2e9;

void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r)
{
    return uniform_int_distribution<int>(l, r) (rd);
}

int n,m;
int q;
ii cost[nmax + 5];
vector<int>adj[nmax + 5];
ii edge[nmax + 5];

int h[nmax + 5];
int par[nmax + 5][23];

int in[nmax + 5];
int out[nmax + 5];
int timer = 0;

void dfs(int u,int dad)
{
    in[u] = ++timer;
    for(auto v:adj[u])
    {
        if(v == dad) continue;
        par[v][0] = u;
        h[v] = h[u] + 1;
        dfs(v,u);
    }
    out[u] = timer;
}

void prepare()
{
    for(int i=1;i<=19;i++)
        for(int j=1;j<=n;j++)
            par[j][i] = par[par[j][i - 1]][i - 1];
}

int LCA(int u,int v)
{
    if(h[v] > h[u])
        swap(u,v);
    for(int i=19;i>=0;i--)
    {
        if(h[par[u][i]] >= h[v])
            u = par[u][i];
    }
    if(u == v) return u;
    for(int i=19;i>=0;i--)
        if(par[u][i] != par[v][i])
    {
        u = par[u][i];
        v = par[v][i];
    }
    return par[u][0];
}

struct infor{
    int s,t,x,y;
}citizen[nmax + 5];

struct parallel{
    int L,R,ANS;
} ans[nmax + 5];


int fen_val[nmax + 5];
int fen_cnt[nmax + 5];
void update(int *bit, int idx, int val)
{
    while(idx <= n)
    {
        bit[idx] += val;
        idx += (idx&(-idx));
    }
}

void updaterange(int *bit, int L,int R,int val)
{
    update(bit, L,val);
    update(bit, R + 1,-val);
}

int get(int *bit, int idx)
{
    int res = 0;
    while(idx)
    {
        res += bit[idx];
        idx -= (idx&(-idx));
    }
    return res;
}

int get_path(int *bit, int u, int v, int lca) {
    return get(bit, in[u]) + get(bit, in[v]) - 2 * get(bit, in[lca]);
}

signed main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;

   for(int i=1;i<n;i++)
   {
        int u,v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
        edge[i].fi = u;
        edge[i].se = v;
   }
   dfs(1,-1);
   prepare();

   for(int i=1;i<=m;i++)
   {
       cin >> cost[i].se >> cost[i].fi;
   }
   sort(cost + 1,cost + 1 + m);

   for(int i=1;i<=q;i++)
   {
       cin >> citizen[i].s >> citizen[i].t >> citizen[i].x >> citizen[i].y;
   }

   for(int i=1;i<=q;i++)
   {
       ans[i].L = 0;
       ans[i].R = m;
       ans[i].ANS = 0;
   }

    vector<int>bucket[nmax + 5];

    while(true)
    {
       bool has_query = false;
       for(int i=0; i<=m; i++) bucket[i].clear();

       for(int i=1;i<=q;i++)
       {
           if(ans[i].L <= ans[i].R)
           {
               has_query = true;
               int mid = (ans[i].L + ans[i].R) >> 1;
               bucket[mid].pb(i);
           }
       }

       if(!has_query) break;

       for(int i=0;i<=n;i++) {
           fen_val[i] = 0;
           fen_cnt[i] = 0;
       }

       for(auto j : bucket[0]) {
           ans[j].ANS = 0;
           ans[j].L = 1;
       }

       for(int i=1;i<=m;i++)
       {
           int u = edge[cost[i].se].fi;
           int v = edge[cost[i].se].se;
           if(par[u][0] == v) swap(u,v);
           updaterange(fen_val, in[v], out[v], cost[i].fi);
           updaterange(fen_cnt, in[v], out[v], 1);

           for(auto j:bucket[i])
           {
               int s = citizen[j].s;
               int t = citizen[j].t;
               int lca = LCA(s, t);

               int sliver = citizen[j].y;
               int need = get_path(fen_val, s, t, lca);
               int checkpoint = get_path(fen_cnt, s, t, lca);

               if(sliver >= need)
               {
                   ans[j].ANS = checkpoint;
                   ans[j].L = i + 1;
               }
               else
                   ans[j].R = i - 1;
                // cout << ans[j].L << " " << ans[j].R << " " << ans[j].ANS;el;
           }

       }
    }
    for(int i=0;i<=n;i++) fen_cnt[i] = 0;
    for(int i=1;i<=m;i++)
    {
        int u = edge[cost[i].se].fi;
        int v = edge[cost[i].se].se;
        if(par[u][0] == v) swap(u,v);
        updaterange(fen_cnt, in[v], out[v], 1);
    }

    for(int i=1;i<=q;i++)
    {
        int s = citizen[i].s;
        int t = citizen[i].t;

        int total = get_path(fen_cnt, s, t, LCA(s, t));
        int gold_needed = total - ans[i].ANS;
//        cout << total << " " << gold_needed << " " << citizen[i].x;el;
        if(citizen[i].x - gold_needed >= 0)
            cout << citizen[i].x - gold_needed;
        else cout << -1;
        el;
    }
}
//Can i get a kiss? And can u make it last forever?

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