Submission #926020

#	Time	Username	Problem	Language	Result	Execution time	Memory
926020		andrei_boaca	Two Currencies (JOI23_currencies)	C++17	100 / 100	1459 ms	54480 KiB

currencies

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
ll n,m,q,in[100005],out[100005],dp[21][100005],par[100005],timp,total[100005],init[100005],niv[100005];
vector<pii> g;
vector<int> muchii[100005];
struct date
{
    ll p,c;
} v[100005];
bool byc(date a, date b)
{
    return a.c<b.c;
}
struct qr
{
    ll a,b,gold,silver,best;
} query[100005];
bool isancestor(int a,int b)
{
    return in[a]<=in[b]&&out[a]>=out[b];
}
int LCA(int a,int b)
{
    if(niv[a]>niv[b])
        swap(a,b);
    if(isancestor(a,b))
        return a;
    for(int i=18;i>=0;i--)
        if(dp[i][a]!=0&&!isancestor(dp[i][a],b))
            a=dp[i][a];
    return par[a];
}
void dfs(int nod)
{
    timp++;
    in[nod]=timp;
    dp[0][nod]=par[nod];
    for(int i=1;i<=18;i++)
        dp[i][nod]=dp[i-1][dp[i-1][nod]];
    for(int i:muchii[nod])
        if(i!=par[nod])
        {
            par[i]=nod;
            niv[i]=niv[nod]+1;
            dfs(i);
        }
    out[nod]=timp;
}
int getnode(pii p)
{
    if(par[p.first]==p.second)
        return p.first;
    return p.second;
}
struct event
{
    ll st,dr,who;
};
bool bymij(event a, event b)
{
    ll mija=(a.st+a.dr)/2;
    ll mijb=(b.st+b.dr)/2;
    return mija<mijb;
}
ll aib[2][100005]; /// 0 -> nr checkpoints, 1 -> suma
int lsb(int x)
{
    return x&(-x);
}
void update(ll ind,ll poz,ll val)
{
    for(ll i=poz;i<=n;i+=lsb(i))
        aib[ind][i]+=val;
}
ll suma(ll ind,ll poz)
{
    ll rez=0;
    for(ll i=poz;i>=1;i-=lsb(i))
        rez+=aib[ind][i];
    return rez;
}
vector<event> ev;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<n;i++)
    {
        ll a,b;
        cin>>a>>b;
        g.push_back({a,b});
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }
    dfs(1);
    for(int i=1;i<=m;i++)
    {
        ll p,c;
        cin>>p>>c;
        p=getnode(g[p-1]);
        v[i]={p,c};
        init[in[p]]++;
        init[out[p]+1]--;
    }
    sort(v+1,v+m+1,byc);
    for(int i=1;i<=n;i++)
        init[i]+=init[i-1];
    for(int i=1;i<=q;i++)
    {
        ll a,b,x,y;
        cin>>a>>b>>x>>y;
        ll lca=LCA(a,b);
        total[i]=init[in[a]]+init[in[b]]-2*init[in[lca]];
        query[i]={a,b,x,y,0};
        ev.push_back({1,m,i});
    }
    while(!ev.empty())
    {
        sort(ev.begin(),ev.end(),bymij);
        for(int i=1;i<=n;i++)
            aib[0][i]=aib[1][i]=0;
        vector<event> aux;
        int poz=1;
        for(auto p:ev)
        {
            ll st=p.st;
            ll dr=p.dr;
            ll mij=(st+dr)/2;
            ll who=p.who;
            ll a=query[who].a;
            ll b=query[who].b;
            ll silver=query[who].silver;
            while(poz<=mij)
            {
                ll nod=v[poz].p;
                ll val=v[poz].c;
                update(0,in[nod],1);
                update(0,out[nod]+1,-1);
                update(1,in[nod],val);
                update(1,out[nod]+1,-val);
                poz++;
            }
            ll lca=LCA(a,b);
            ll s=suma(1,in[a])+suma(1,in[b])-2*suma(1,in[lca]);
            if(s<=silver)
            {
                query[who].best=suma(0,in[a])+suma(0,in[b])-2*suma(0,in[lca]);
                st=mij+1;
            }
            else
                dr=mij-1;
            if(st<=dr)
                aux.push_back({st,dr,who});
        }
        ev=aux;
    }
    for(int i=1;i<=q;i++)
    {
        ll rem=total[i]-query[i].best;
        if(rem>query[i].gold)
            cout<<-1<<'\n';
        else
            cout<<query[i].gold-rem<<'\n';
    }
    return 0;
}

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