Submission #862179

#	Time	Username	Problem	Language	Result	Execution time	Memory
862179		imarn	Two Currencies (JOI23_currencies)	C++14	100 / 100	3057 ms	211180 KiB

currencies

#include "bits/stdc++.h"
#define f first
#define s second
#define ll long long
#define pb push_back
#define pii pair<ll,ll>
using namespace std;
const int N=1e5+5;
vector<pair<int,vector<ll>>>g[N];
int sz[N],head[N],pr[N],dep[N],idl[N],idr[N];
pair<ll,pii> a[4*N];
vector<pair<int,pii>>t[16*N];
int n;
void build(int i,int l,int r){
    if(l==r)return void(t[i].pb({a[l].s.s,{a[l].f,a[l].f}}));
    int m=(l+r)>>1;
    build(2*i,l,m);build(2*i+1,m+1,r);
    int li=0,ri=0;
    while(li<t[2*i].size()&&ri<t[2*i+1].size()){
        if(t[2*i][li].f<t[2*i+1][ri].f)t[i].pb({t[2*i][li].f,{t[2*i][li].s.f,t[2*i][li].s.f}}),li++;
        else t[i].pb({t[2*i+1][ri].f,{t[2*i+1][ri].s.f,t[2*i+1][ri].s.f}}),ri++;
    }while(li<t[2*i].size())t[i].pb({t[2*i][li].f,{t[2*i][li].s.f,t[2*i][li].s.f}}),li++;
    while(ri<t[2*i+1].size())t[i].pb({t[2*i+1][ri].f,{t[2*i+1][ri].s.f,t[2*i+1][ri].s.f}}),ri++;
    for(int j=1;j<t[i].size();j++)t[i][j].s.s=t[i][j-1].s.s+t[i][j].s.f;
}
pii qr(int i,int l,int r,int tl,int tr,int x){
    if(r<tl||l>tr)return {0,0};
    if(r<=tr&&l>=tl){
        int le=0,re=t[i].size()-1;
        if(x<t[i][0].f)return {0,0};
        while(le<re){
            int md=(le+re+1)>>1;
            if(t[i][md].f<=x)le=md;
            else re=md-1;
        }return {t[i][le].s.s,le+1};
    }
    int m=(l+r)>>1;
    pii qll=qr(2*i,l,m,tl,tr,x),qrr=qr(2*i+1,m+1,r,tl,tr,x);
    return {qll.f+qrr.f,qll.s+qrr.s};
}
int dfs(int u,int p){
    sz[u]=1;
    pr[u]=p;
    for(auto v:g[u]){
        if(v.f==p)continue;
        dep[v.f]=dep[u]+1;
        sz[u]+=dfs(v.f,u);
    }return sz[u];
}int cnt=1;
void hld(int u,vector<ll> w,int p,int h){
    idl[u]=cnt;
    for(auto it : w){
        a[cnt].f = it;
        a[cnt].s.f = cnt++;
    }idr[u]=cnt-1;
    head[u]=h;
    int x=-1,y=-1;vector<ll>z;
    for(auto v:g[u]){
        if(v.f==p)continue;
        if(sz[v.f]>y)y=sz[v.f],x=v.f,z=v.s;
    }if(x==-1)return;
    hld(x,z,u,h);
    for(auto v:g[u]){
        if(v.f==p||v.f==x)continue;
        hld(v.f,v.s,u,v.f);
    }
}
pii path(int x,int y,ll v,pii res={0,0}){
    while(head[x]!=head[y]){
        if(dep[head[x]]<dep[head[y]])swap(x,y);
        pii tmp=qr(1,1,cnt-1,idl[head[x]],idr[x],v);
        res.f+=tmp.f;res.s+=tmp.s;
        x=pr[head[x]];
    }if(dep[x]>dep[y])swap(x,y);
    pii tmp=qr(1,1,cnt-1,idr[x]+1,idr[y],v);
    res.f+=tmp.f;res.s+=tmp.s;
    return res;
}pii road[N];vector<ll> W[N];
bool cmp(pair<ll,pii> x,pair<ll,pii> y){
    return x.s.f<y.s.f;
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int m,q;cin>>n>>m>>q;
	for(int i=1;i<=n-1;i++)cin>>road[i].f>>road[i].s;
	for(int i=1;i<=n;i++)W[i].pb(0);
	for(int i=1;i<=m;i++){
        int u;ll w;cin>>u>>w;
        W[u].pb(w);
	}for(int i=1;i<=n-1;i++)g[road[i].f].pb({road[i].s,W[i]}),g[road[i].s].pb({road[i].f,W[i]});
	dfs(1,1);hld(1,{0},1,1);
	sort(a+1,a+cnt);
	for(int i=1;i<cnt;i++)a[i].s.s=i;
	sort(a+1,a+cnt,cmp);
	build(1,1,cnt-1);
	while(q--){
        int st,ed;ll x,y;cin>>st>>ed>>x>>y;
        ll dist = path(st,ed,cnt).s;
        ll l=1,r=cnt-1;
        while(l<r){
            ll md=(l+r+1)>>1;
            pii tmp = path(st,ed,md);
            if(tmp.f>y)r=md-1;
            else l=md;
        }pii tmp = path(st,ed,l);
        if(tmp.s+x>=dist)cout<<x-dist+tmp.s<<"\n";
        else cout<<-1<<"\n";
	}
}

Compilation message (stderr)

currencies.cpp: In function 'void build(int, int, int)':
currencies.cpp:19:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     while(li<t[2*i].size()&&ri<t[2*i+1].size()){
      |           ~~^~~~~~~~~~~~~~
currencies.cpp:19:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     while(li<t[2*i].size()&&ri<t[2*i+1].size()){
      |                             ~~^~~~~~~~~~~~~~~~
currencies.cpp:22:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     }while(li<t[2*i].size())t[i].pb({t[2*i][li].f,{t[2*i][li].s.f,t[2*i][li].s.f}}),li++;
      |            ~~^~~~~~~~~~~~~~
currencies.cpp:23:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     while(ri<t[2*i+1].size())t[i].pb({t[2*i+1][ri].f,{t[2*i+1][ri].s.f,t[2*i+1][ri].s.f}}),ri++;
      |           ~~^~~~~~~~~~~~~~~~
currencies.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int j=1;j<t[i].size();j++)t[i][j].s.s=t[i][j-1].s.s+t[i][j].s.f;
      |                 ~^~~~~~~~~~~~
currencies.cpp: In function 'void hld(int, std::vector<long long int>, int, int)':
currencies.cpp:54:25: warning: operation on 'cnt' may be undefined [-Wsequence-point]
   54 |         a[cnt].s.f = cnt++;
      |                      ~~~^~
currencies.cpp:54:25: warning: operation on 'cnt' may be undefined [-Wsequence-point]

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