Submission #1014760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014760		alexdd	Two Currencies (JOI23_currencies)	C++17	100 / 100	544 ms	47900 KiB

currencies

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
int n,m,q;

int aib[100005][2];
int qry(int p, int c)
{
    int aux=0;
    for(int i=p;i>0;i-=(i&(-i)))
        aux += aib[i][c];
    return aux;
}
void upd(int p, int val, int c)
{
    for(int i=p;i<=n;i+=(i&(-i)))
        aib[i][c] += val;
}

vector<int> con[100005];
pair<int,int> edges[100005];
int tin[100005],tout[100005],timer;
int parent[100005];
vector<pair<int,int>> obstacole;
pair<int,int> drum[100005],bani[100005];
int lc[100005];
int anc[100005][17];
int rez[100005];
void dfs_init(int nod)
{
    tin[nod]=++timer;
    for(auto adj:con[nod])
    {
        if(adj!=parent[nod])
        {
            parent[adj]=nod;
            dfs_init(adj);
        }
    }
    tout[nod]=timer;
}
bool isanc(int x, int y)
{
    return (tin[x]<=tin[y] && tout[x]>=tout[y]);
}
int lca(int x, int y)
{
    if(isanc(x,y))
        return x;
    if(isanc(y,x))
        return y;
    for(int p=16;p>=0;p--)
        if(!isanc(anc[x][p],y))
            x = anc[x][p];
    return anc[x][0];
}
int poz;
void cautare_binara(int st, int dr, vector<int> ids)
{
    if(st>dr || ids.empty())
        return;
    int mij=(st+dr)/2;
    while(poz<mij)
    {
        poz++;
        upd(tin[obstacole[poz].second], obstacole[poz].first, 0);
        upd(tout[obstacole[poz].second]+1, -obstacole[poz].first, 0);

        upd(tin[obstacole[poz].second], -1, 1);
        upd(tout[obstacole[poz].second]+1, +1, 1);
    }
    while(poz>mij)
    {
        upd(tin[obstacole[poz].second], -obstacole[poz].first, 0);
        upd(tout[obstacole[poz].second]+1, obstacole[poz].first, 0);

        upd(tin[obstacole[poz].second], +1, 1);
        upd(tout[obstacole[poz].second]+1, -1, 1);
        poz--;
    }
    vector<int> tole,tori;
    for(auto x:ids)
    {
        int aux0 = qry(tin[drum[x].first],0) + qry(tin[drum[x].second],0) - 2*qry(tin[lc[x]],0);
        int aux1 = qry(tin[drum[x].first],1) + qry(tin[drum[x].second],1) - 2*qry(tin[lc[x]],1);
        //cout<<aux0<<" aux0\n";
        if(aux0 <= bani[x].second)
        {
            rez[x] = min(rez[x], aux1);
            tori.push_back(x);
        }
        else
            tole.push_back(x);
    }
    if(st<dr)
    {
        cautare_binara(st,mij,tole);
        cautare_binara(mij+1,dr,tori);
    }
}
signed main()
{
    cin>>n>>m>>q;
    int a,b;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        edges[i] = {a,b};
        con[a].push_back(b);
        con[b].push_back(a);
    }
    dfs_init(1);
    for(int i=1;i<n;i++)
        if(parent[edges[i].first]==edges[i].second)
            swap(edges[i].first, edges[i].second);

    for(int i=1;i<=n;i++)
        anc[i][0]=parent[i];
    anc[1][0]=1;
    for(int p=1;p<17;p++)
        for(int i=1;i<=n;i++)
            anc[i][p] = anc[anc[i][p-1]][p-1];

    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        obstacole.push_back({b,edges[a].second});
        upd(tin[edges[a].second], +1, 1);
        upd(tout[edges[a].second]+1, -1, 1);
    }
    sort(obstacole.begin(),obstacole.end());
    vector<int> ids;
    for(int i=1;i<=q;i++)
    {
        cin>>drum[i].first>>drum[i].second>>bani[i].first>>bani[i].second;
        lc[i] = lca(drum[i].first, drum[i].second);
        ids.push_back(i);
        rez[i] = qry(tin[drum[i].first],1) + qry(tin[drum[i].second],1) - 2*qry(tin[lc[i]],1);
    }
    poz=-1;
    cautare_binara(0,m-1,ids);
    for(int i=1;i<=q;i++)
    {
        if(rez[i] > bani[i].first)
            cout<<-1<<"\n";
        else
            cout<<bani[i].first-rez[i]<<"\n";
    }
    return 0;
}

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