Submission #784601

#	Time	Username	Problem	Language	Result	Execution time	Memory
784601		MohamedAliSaidane	Two Currencies (JOI23_currencies)	C++14	100 / 100	1893 ms	54892 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(),(x).end()

const int nax = 1e5 + 4;


int n, m, q, k = 1;
vector<pii> adj[nax];
vector<pair<ll,int>> checkp;
vector<ll> st, lazy;
int eul[nax], ed[nax], sp[nax][20], d[nax], head[nax];
int S[nax], T[nax], C[nax];
ll X[nax], Y[nax];
int cureul = -1;
void propagate(int p, int l, int r)
{
    if(lazy[p] != 0)
    {
        if(l != r)
        {
            lazy[2 * p] +=lazy[p];
            lazy[2 * p + 1] += lazy[p];
        }
        st[p] += lazy[p] * 1ll * (r - l + 1);
        lazy[p] = 0ll;
    }
}
void update(int p, int l, int r, int i, int j, ll val)
{
    propagate(p, l, r);
    if(i > j)
        return;
    if(l >= i && r<= j)
    {
        lazy[p] += val;
        propagate(p, l, r);
        return ;
    }
    int mid = (l + r)/2;
    update(2 * p, l, mid, i, min(j, mid), val);
    update(2 * p + 1, mid + 1, r, max(i, mid + 1), j, val);
    ll lsubtree = st[2 * p] + lazy[2 * p] * 1ll * (mid - l + 1ll);
    ll rsubtree = st[2 * p + 1] + lazy[2 * p + 1] * 1ll * (r - mid);
    st[p] = lsubtree + rsubtree;
}
ll query(int p, int l, int r, int i, int j)
{
    propagate(p, l,r );
    if(i > j)
        return 0ll;
    if(l >= i && r <= j)
        return st[p];
    int mid = (l  + r)/2;
    return query(2 * p, l, mid, i, min(j, mid))
        + query(2 * p + 1, mid + 1, r, max(i, mid + 1), j);
}
void dfs(int x, int p = 0)
{
    sp[x][0] = p;
    d[x]=  d[p] + 1;
    eul[x] = ++cureul;
    for(auto e: adj[x])
    {
        if(e.ff == p)
            continue;
        head[e.ss] = e.ff;
        dfs(e.ff, x);
    }
    ed[x]= cureul;
}
void build()
{
    for(int j = 1; j < 20; j++)
        for(int i =1; i <= n; i++)
            sp[i][j] = sp[sp[i][j - 1]][j - 1];
}
int jump(int a, int k)
{
    for(int i = 0; i < 20; i++)
        if((1 << i) & k)
            a = sp[a][i];
    return a;
}
int lca(int a, int b)
{
    if(d[a] < d[b])
        swap(a, b);
    a = jump(a, d[a] - d[b]);
    if(a == b)
        return a;
    for(int i = 19; i >= 0; i--)
        if(sp[a][i] != sp[b][i])
            a = sp[a][i], b=  sp[b][i];
    return sp[a][0];
}
int cur = -1;
vector<vector<int>> QE;
int rep[nax], ans[nax];
vector<int> COR[nax];

void bsearch(int l, int r, int idx =0)
{
    if(QE[idx].empty())
        return ;
    if(l > r)
    {
        QE[idx].clear();
        return ;
    }
   // cout << l << ' ' << r << endl;
    int mid = (l + r)/2;
    if(cur < mid)
    {
        for(cur++; cur <= mid; cur++)
        {
            int x = checkp[cur].ss;
            ll  V = checkp[cur].ff;
            update(1, 0,  k - 1, eul[x], ed[x], V);
        }
        cur--;
    }
    else
    {
        for(; cur > mid; cur--)
        {
            int x = checkp[cur].ss;
            ll  V = checkp[cur].ff;
            update(1, 0,  k - 1, eul[x], ed[x], -V);
        }

    }
    vector<int> L, R;
    for(auto e: QE[idx])
    {
        ll path = query(1, 0, k - 1, eul[S[e]], eul[S[e]])
            + query(1, 0,  k - 1, eul[T[e]], eul[T[e]])
            - 2ll * query(1, 0, k - 1, eul[C[e]], eul[C[e]]);
        if(path <= Y[e])
        {
            //cout <<mid << ' ' << e << ' ' << path << ' ' << S[e] << ' ' << T[e] <<' ' << C[e] <<  endl;
            rep[e] = mid;
            R.pb(e);
        }
        else
            L.pb(e);
    }
    QE[idx].clear();
    if(!L.empty())
    {
        QE.pb(L);
        L.clear();
        bsearch(l, mid - 1, (int)(QE.size()) - 1);
    }
    if(!R.empty())
    {
        QE.pb(R);
        R.clear();
        bsearch(mid + 1, r, (int)(QE.size()) - 1);
    }
    return;
}
void solve()
{
    cin >> n >> m >> q;
    for(int i= 1; i <  n; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].pb({b, i});
        adj[b].pb({a, i});
    }
    dfs(1, 0);
    build();
    while(k < n)
        k = (k << 1);
    st.assign(2 * k + 1, 0ll);
    lazy.assign(2 * k + 1, 0ll);
    for(int i = 0; i < m; i++)
    {
        int p; cin >> p;
        ll c; cin >> c;
        checkp.pb({c, head[p]});
    }
    sort(all(checkp));
    QE.pb({});
    for(int i = 0; i < q; i++)
    {
        cin >> S[i] >> T[i] >> X[i] >> Y[i];
        C[i]=  lca(S[i], T[i]);
        QE[0].pb(i);
        rep[i] = -1;
    }
    bsearch(0, m - 1);
    st.assign(2 * k + 1, 0ll);
    lazy.assign(2 * k + 1, 0ll);
    for(int i =0; i < q; i++)
        COR[rep[i] + 1].pb(i);
    for(int i = m - 1; i >= 0; i--)
    {
        int x = checkp[i].ss;
        update(1, 0, k- 1, eul[x], ed[x], 1);
        for(auto e: COR[i])
        {
            int a= query(1, 0, k -1, eul[S[e]], eul[S[e]]);
            int b = query(1, 0, k - 1, eul[T[e]], eul[T[e]]);
            int c = query(1, 0, k -1, eul[C[e]], eul[C[e]]);
            ans[e] = a + b - 2 * c;
            //cout << e << ' ' << ans[e] << '\n';
        }
    }
    for(int i = 0; i< q; i++)
    {
        if(ans[i] > X[i])
            cout << "-1\n";
        else
            cout << X[i] - ans[i] << '\n';
    }
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tt = 1;
    while(tt--)
        solve();
}

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