Submission #1127359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127359		lamlamjjdo	Two Currencies (JOI23_currencies)	C++20	100 / 100	1448 ms	28432 KiB

currencies

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
vector<int>a[100010];
int pr[20][100010];
int h[100010];
int cr=0;
int nums[100010],tail[100010];
void pre(int i,int c){
    cr++;
    nums[i]=cr;
    h[i]=h[c]+1;
    pr[0][i]=c;
    for(int o=1;o<17;o++){
        pr[o][i]=pr[o-1][pr[o-1][i]];
    }
    for(auto o:a[i]){
        if(o!=c)pre(o,i);
    }
    tail[i]=cr;
}
int lca(int i,int j){
    if(h[i]>h[j])swap(i,j);
    for(int o=16;o>=0;o--){
        if(h[i]+(1<<o)<=h[j])j=pr[o][j];
    }
    if(i==j)return i;
    for(int o=16;o>=0;o--){
        if(pr[o][i]!=pr[o][j]){
            i=pr[o][i];
            j=pr[o][j];
        }
    }
    return pr[0][i];
}
struct IT{
    long long f[500000];
    void re(){
        for(int i=4*n;i>=1;i--){
            f[i]=0;
        }
    }
    void cn(int id,int l,int r,int u,int v,int o){
        if(l>v||r<u)return ;
        if(l>=u&&r<=v){
            f[id]+=o;
            return ;
        }
        int mid=(l+r)/2;
        cn(id*2,l,mid,u,v,o);
        cn(id*2+1,mid+1,r,u,v,o);
    }
    long long gtt(int id,int l,int r,int o){
        if(l==r)return f[id];
        int mid=(l+r)/2;
        f[id*2]+=f[id];
        f[id*2+1]+=f[id];
        f[id]=0;
        if(o<=mid)return gtt(id*2,l,mid,o);
        else return gtt(id*2+1,mid+1,r,o);
    }
    long long gt(int i){
        return gtt(1,1,n,nums[i]);
    }
};
vector<pair<int,int>>g;
int xx[100010],yy[100010];

int s[100010],e[100010],va[100010],p[100010];
long long ba[100010];
int res[100010];
int ll[100010],rr[100010];
vector<pair<int,int>>xet;
IT lma;
void xl(int i,int mid){
    if(lma.gt(s[i])+lma.gt(e[i])-2*lma.gt(p[i])<=ba[i]){
        res[i]=mid;
        ll[i]=mid+1;
    }
    else rr[i]=mid-1;
}
void sol(){
    lma.re();
    xet.clear();
    for(int i=1;i<=q;i++){
        if(ll[i]<=rr[i])xet.push_back({(ll[i]+rr[i])/2,i});
    }
    sort(xet.begin(),xet.end());
    int j=0;
    int cr=0;
    for(auto o:g){
        int i=o.second;
        lma.cn(1,1,n,nums[yy[i]],tail[yy[i]],o.first);
        while(j<xet.size()){
            if(xet[j].first==cr){
                xl(xet[j].second,xet[j].first);
                j++;
            }
            else break;
        }
        cr++;
    }
}
int asw1[100010],asw2[100010];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen("c.INP","r")){
        freopen("c.INP","r",stdin);
        freopen("c.OUT","w",stdout);
    }
    cin >>n>>m>>q;
    for(int i=1;i<n;i++){
        cin >>xx[i]>>yy[i];
        a[xx[i]].push_back(yy[i]);
        a[yy[i]].push_back(xx[i]);
    }
    pre(1,0);
    for(int i=1;i<=m;i++){
        int x,y;
        cin >>x>>y;
        if(h[xx[x]]>h[yy[x]])swap(xx[x],yy[x]);
        g.push_back({y,x});
    }
    sort(g.begin(),g.end());
    for(int i=1;i<=q;i++){
        cin >>s[i]>>e[i]>>va[i]>>ba[i];
        p[i]=lca(s[i],e[i]);
        res[i]=-1;
        ll[i]=0;
        rr[i]=m-1;
    }
    for(int i=1;i<=18;i++){
        sol();
    }
    xet.clear();
    lma.re();
    for(int i=1;i<=q;i++){
        if(res[i]!=-1)xet.push_back({res[i],i});
    }
    sort(xet.begin(),xet.end());
    int j=0;
    int cr=0;
    for(auto o:g){
        int i=o.second;
        lma.cn(1,1,n,nums[yy[i]],tail[yy[i]],1);
        while(j<xet.size()){
            if(xet[j].first==cr){
                int u=xet[j].second;
                asw1[u]=lma.gt(s[u])+lma.gt(e[u])-2*lma.gt(p[u]);
                j++;
            }
            else break;
        }
        cr++;
    }
    for(int i=1;i<=q;i++){
        cout <<max(va[i]-lma.gt(s[i])-lma.gt(e[i])+2*lma.gt(p[i])+asw1[i],-1ll)<<'\n';
    }
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen("c.INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~
currencies.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen("c.OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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