Submission #778884

#	Time	Username	Problem	Language	Result	Execution time	Memory
778884		onepunchac168	Two Currencies (JOI23_currencies)	C++14	100 / 100	1541 ms	90544 KiB

currencies

// created by Dinh Manh Hung
// onepunchac168
// THPT CHUYEN HA TINH
// HA TINH, VIET NAM
 
#include <bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
//#pragma GCC target("sse4,avx2,fma")
#define task ""
#define ldb long double
#define pb push_back
#define fi first
#define se second
#define pc pop_back()
#define all(x) begin(x),end(x)
#define uniquev(v) v.resize(unique(all(v))-v.begin())
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define cntbit(v) __builtin_popcountll(v)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) ((1LL*a*b)/__gcd(a,b))
#define mask(x) (1LL<<(x))
#define readbit(x,i) ((x>>i)&1)
#define ins insert
 
typedef long long ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
typedef pair <ii,ii> iiii;
 
ll dx[]= {1,-1,0,0,1,-1,1,-1};
ll dy[]= {0,0,-1,1,1,-1,-1,1};
 
const ldb PI = acos (-1);
//const ll mod=978846151;
//const ll base=29;
const int maxn=1e6+5;
const int mod=1e9+7;
const char nl = '\n';
inline int ReadInt()
{
    char co;
    for (co = getchar(); co < '0' || co > '9'; co = getchar());
    int xo = co - '0';
    for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
        xo = xo * 10 + co - '0';
    return xo;
}
 
void WriteInt(int xo)
{
    if (xo > 9)
        WriteInt(xo / 10);
    putchar(xo % 10 + '0');
}
/* END OF TEMPLATE*/
 
// ================= Solution =================//
const int N=1e5+5;
ll n,m,k;
vector <ll> vt[N];
ll p[N],c[N];
vector <ll> opt;
struct Node {
    int left,right;
    ll val;
    ll vala;
    Node(int left,int right,ll val,ll vala){
        this->left=left;
        this->right=right;
        this->val=val;
        this->vala=vala;
    }
    Node(){
 
    }
} T[N*24+5];
int ver[N];
vector <ll> tmp[N];
int Nnode=0;
int update(int oldnode,int l,int r,int u,ll val)
{
    if (l==r)
    {
        Nnode++;
        T[Nnode]=Node(0,0,val,val*opt[r-1]);
        return Nnode;
    }
    int mid=(l+r)/2;
    Nnode++;
    int newnode=Nnode;
    if (u<=mid)
    {
        T[newnode].left=update(T[oldnode].left,l,mid,u,val);
        T[newnode].right=T[oldnode].right;
        T[newnode].val=T[T[newnode].left].val+T[T[newnode].right].val;
        T[newnode].vala=T[T[newnode].left].vala+T[T[newnode].right].vala;
    }
    else
    {
        T[newnode].right=update(T[oldnode].right,mid+1,r,u,val);
        T[newnode].left=T[oldnode].left;
        T[newnode].val=T[T[newnode].left].val+T[T[newnode].right].val;
        T[newnode].vala=T[T[newnode].left].vala+T[T[newnode].right].vala;
    }
    return newnode;
 
}
ll query(int node,int l,int r,int u,int v)
{
    if (l>v||r<u)
    {
        return 0;
    }
    if (l>=u&&r<=v)
    {
        return T[node].val;
    }
    int mid=(l+r)/2;
    ll a1=query(T[node].left,l,mid,u,v);
    ll a2=query(T[node].right,mid+1,r,u,v);
    return a1+a2;
}
ll querya(int node,int l,int r,int u,int v)
{
    if (l>v||r<u)
    {
        return 0;
    }
    if (l>=u&&r<=v)
    {
        return T[node].vala;
    }
    int mid=(l+r)/2;
    ll a1=querya(T[node].left,l,mid,u,v);
    ll a2=querya(T[node].right,mid+1,r,u,v);
    return a1+a2;
}
map<ii,ll> mp;
ll cha[N][25];
ll sz[N];
void dfs(int u,int vv)
{
    for (auto v:vt[u])
    {
        if (v==vv)
        {
            continue;
        }
        cha[v][0]=u;
        sz[v]=sz[u]+1;
        for (int i=1;i<=20;i++)
        {
            cha[v][i]=cha[cha[v][i-1]][i-1];
        }
        dfs(v,u);
    }
}
void dfs1(int u,int vv)
{
    ver[u]=ver[vv];
    for (auto v:tmp[u])
    {
        ll aa=lower_bound(opt.begin(),opt.end(),v)-opt.begin()+1;
        ll bb=query(ver[u],1,opt.size(),aa,aa);
        ver[u]=update(ver[u],1,opt.size(),aa,bb+1);
    }
    for (auto v:vt[u])
    {
        if (v==vv)
        {
            continue;
        }
        dfs1(v,u);
    }
}
ll lca(int u,int v)
{
    if (sz[u]>sz[v]){swap(u,v);}
    for (int i=20;i>=0;i--)
    {
        if (sz[v]-mask(i)>=sz[u])
        {
            v=cha[v][i];
        }
    }
    if (u==v){return u;}
    for (int i=20;i>=0;i--)
    {
        if (cha[u][i]!=cha[v][i])
        {
            u=cha[u][i];
            v=cha[v][i];
        }
    }
    if (u!=v)
    {
        u=cha[u][0];
        v=cha[v][0];
    }
    return u;
}
ll ua[N],va[N];
void optmushnpr()
{
    cin>>n>>m>>k;
    T[0]=Node(0,0,0,0);
    ver[0]=0;
    for (int i=1;i<n;i++)
    {
        cin>>ua[i]>>va[i];
        vt[ua[i]].pb(va[i]);
        vt[va[i]].pb(ua[i]);
    }
    dfs(1,0);
    for (int i=1;i<=m;i++)
    {
        cin>>p[i]>>c[i];
        ll id=p[i];
        if (sz[ua[id]]>sz[va[id]])
        {
            tmp[ua[id]].pb(c[i]);
        }
        else
        {
            tmp[va[id]].pb(c[i]);
        }
        opt.pb(c[i]);
    }
    sort (opt.begin(),opt.end());
    uniquev(opt);
    dfs1(1,0);
    while (k--)
    {
        ll x,y,u,v;
        cin>>u>>v>>x>>y;
        ll left=1;ll right=opt.size();
        ll parent=lca(u,v);
        ll ans=opt.size();
        ll sum=querya(ver[u],1,opt.size(),1,opt.size())+querya(ver[v],1,opt.size(),1,opt.size())-2*querya(ver[parent],1,opt.size(),1,opt.size());
        while (left<=right)
        {
            ll mid=(left+right)/2;
            ll a1=querya(ver[u],1,opt.size(),1,mid);
            ll a2=querya(ver[v],1,opt.size(),1,mid);
            ll a3=querya(ver[parent],1,opt.size(),1,mid);
            if (a1+a2-2*a3>=y)
            {
                sum=a1+a2-2*a3;
                ans=mid;
                right=mid-1;
            }
            else left=mid+1;
        }
        ll ok=0;
        if (ans!=0)
        {
            if (sum>y)
            {
                ll h=(sum-y)/opt[ans-1];
                if (h*opt[ans-1]<sum-y)
                {
                    h++;
                }
                ok=h;
            }
        }
        ll a1=query(ver[u],1,opt.size(),ans+1,opt.size());
        ll a2=query(ver[v],1,opt.size(),ans+1,opt.size());
        ll a3=query(ver[parent],1,opt.size(),ans+1,opt.size());
        ok+=a1+a2-2*a3;
        if (ok<=x)
        {
            cout<<x-ok<<nl;
        }
        else cout<<-1<<nl;
    }
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(task".inp","r")){
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);}
    int t;
    t=1;
    //cin>>t;
    while (t--){optmushnpr();}
}
 
// goodbye see ya

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:286:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  286 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:287:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  287 |     freopen(task".out","w",stdout);}
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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