Submission #1263448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263448		denislav	Two Currencies (JOI23_currencies)	C++20	100 / 100	336 ms	73928 KiB

currencies

# include <iostream>
# include <vector>
# include <algorithm>
//# define endl "\n"
using namespace std;

const int MAX=1e5+11,LOG=20;

int n,m,q;
pair<int,int> edges[MAX];
vector<int> adj[MAX];

int h[MAX];
int st[MAX][LOG];
void dfs_init(int curr, int par)
{
    for(int nxt: adj[curr])
    {
        if(nxt==par) continue;
        h[nxt]=h[curr]+1;
        st[nxt][0]=curr;
        dfs_init(nxt,curr);
    }
}

int get_lca(int u, int v)
{
    if(h[u]<h[v]) swap(u,v);
    for(int j=LOG-1;j>=0;j--)
    {
        if(h[u]-(1<<j)>=h[v]) u=st[u][j];
    }
    if(u==v) return u;

    for(int j=LOG-1;j>=0;j--)
    {
        if(h[u]-(1<<j)>=0 and st[u][j]!=st[v][j])
        {
            u=st[u][j];
            v=st[v][j];
        }
    }
    return st[u][0];
}

void lca_precalc()
{
    dfs_init(1,0);
    for(int j=1;j<LOG;j++)
    {
        for(int i=1;i<=n;i++)
        {
            if(h[i]-(1<<j)<0) continue;
            st[i][j]=st[st[i][j-1]][j-1];
        }
    }
}

pair<int,int> cp[MAX];
int real_value[MAX];
vector<int> cpts[MAX];
int cnt_cpts[MAX];

struct node
{
    long long cost,cnt;
    node(){cost=0;cnt=0;}
    node(long long _cost, long long _cnt) {cost=_cost;cnt=_cnt;}
    node friend operator + (node A, node B)
    {
        return {A.cost+B.cost,A.cnt+B.cnt};
    }
};

const int Tsz=MAX*LOG;

int ct,M;
int roots[MAX];
node tree[Tsz];
int lv[Tsz];
int rv[Tsz];

int update(int pos, int d, int v, int l=1, int r=M)
{
    if(l==r)
    {
        ct++;
        tree[ct]=tree[v];
        tree[ct].cost+=d;
        tree[ct].cnt++;
        return ct;
    }

    int mid=(l+r)/2;
    if(pos<=mid)
    {
        ct++;
        int v2=ct;
        lv[v2]=update(pos,d,lv[v],l,mid);
        rv[v2]=rv[v];
        tree[v2]=tree[lv[v2]]+tree[rv[v2]];
        return v2;
    }
    else
    {
        ct++;
        int v2=ct;
        lv[v2]=lv[v];
        rv[v2]=update(pos,d,rv[v],mid+1,r);
        tree[v2]=tree[lv[v2]]+tree[rv[v2]];
        return v2;
    }
}

void dfs(int curr, int par)
{
    cnt_cpts[curr]=cpts[curr].size()+cnt_cpts[par];
    roots[curr]=roots[par];
    for(int x: cpts[curr]) roots[curr]=update(x,real_value[x],roots[curr]);

    for(int nxt: adj[curr])
    {
        if(nxt==par) continue;
        dfs(nxt,curr);
    }
}

long long query(long long k, int u, int v, int lca, int l=1, int r=M)
{
    //cout<<k<<" "<<l<<" "<<r<<" "<<real_value[l]<<endl;

    if(l==r)
    {
        long long cnt=tree[u].cnt+tree[v].cnt-tree[lca].cnt*2;
        return min(k/real_value[l],cnt);
    }

    long long cost=tree[lv[u]].cost+tree[lv[v]].cost-tree[lv[lca]].cost*2;
    long long cnt=tree[lv[u]].cnt+tree[lv[v]].cnt-tree[lv[lca]].cnt*2;
    //cout<<cost<<" "<<cnt<<endl;

    int mid=(l+r)/2;
    if(cost>k) return query(k,lv[u],lv[v],lv[lca],l,mid);
    else return cnt+query(k-cost,rv[u],rv[v],rv[lca],mid+1,r);
}

int main()
{
    ios_base::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;
        edges[i]={u,v};
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    lca_precalc();

    vector<pair<int,int>> temp;
    for(int i=1;i<=m;i++)
    {
        cin>>cp[i].first>>cp[i].second;
        temp.push_back({cp[i].second,i});
    }
    sort(temp.begin(),temp.end());
    int last=-1,ctt=0;
    for(pair<int,int> pa: temp)
    {
        if(pa.first!=last)
        {
            ctt++;
            real_value[ctt]=pa.first;
            last=pa.first;
        }
        cp[pa.second].second=ctt;
    }
    M=ctt;
    for(int i=1;i<=m;i++)
    {
        int u=edges[cp[i].first].first;
        int v=edges[cp[i].first].second;
        if(h[u]>h[v]) swap(u,v);
        cpts[v].push_back(cp[i].second);
    }

    roots[0]=0;
    dfs(1,0);

    while(q--)
    {
        int u,v,lca;
        long long x,y;
        cin>>u>>v>>x>>y;
        lca=get_lca(u,v);

        //cout<<"->"<<lca<<endl;

        long long ans=(cnt_cpts[u]+cnt_cpts[v]-cnt_cpts[lca]*2)-query(y,roots[u],roots[v],roots[lca]);
        x-=ans;
        if(x>=0) cout<<x<<"\n";
        else cout<<-1<<"\n";
    }

    return 0;
}

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