Submission #1261285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261285		erering	Two Currencies (JOI23_currencies)	C++20	100 / 100	2594 ms	410128 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pb push_back
const int N=2e5+5;
vector<int> adj[N];
pair<int,int> road[N],p[N];
map<pair<int,int>,int> c;
int up[N][20],depth[N],gold[N],offset=1,tin[N],tout[N],tim=0;
void dfs(int node,int par,int d){
    depth[node]=d;
    up[node][0]=par;
    for(int j=1;j<20;j++)up[node][j]=up[up[node][j-1]][j-1];
    tin[node]=tim++;
    gold[tin[node]]+=gold[tin[par]];
    for(auto i:adj[node]){
        if(i==par)continue;
        gold[tim]+=c[{node,i}];
        dfs(i,node,d+1);
    }
    tout[node]=tim++;
}
int lca(int a,int b){
    if(depth[a]<depth[b])swap(a,b);
    for(int j=19;j>=0;j--){
        if(up[a][j]==0)continue;
        if(depth[up[a][j]]>depth[b])a=up[a][j];
    }
    if(depth[a]>depth[b])a=up[a][0];
    if(a==b)return a;
    for(int j=19;j>=0;j--){
        if(up[a][j]!=up[b][j]){
            a=up[a][j];
            b=up[b][j];
        }
    }
    return up[a][0];
}
struct node{
    pair<int,int> sum={0,0},lazy={0,0}; //lazy.first=plus silver lazy.second=minus gold
    node* l=NULL;
    node* r=NULL;
};
node* root[N];
void build(node *cur,int l,int r){
    if(l==r){
        cur->sum.second+=gold[l];
        return;
    }
    cur->l=new node;
    cur->r=new node;
    int mid=(l+r)/2;
    build(cur->l,l,mid);
    build(cur->r,mid+1,r);
    cur->sum.second=cur->r->sum.second+cur->l->sum.second;
}
node* insert(node* cur,int qlo,int qhi,int l,int r,int plus){
    if(l>qhi || r<qlo)return cur;
    node* x=new node(*cur);
    if(l>=qlo && r<=qhi){
        x->sum.first+=plus;
        x->sum.second--;
        x->lazy.first+=plus; x->lazy.second--;
        return x;
    }
    int mid=(l+r)/2;
    x->l=insert(x->l,qlo,qhi,l,mid,plus);
    x->r=insert(x->r,qlo,qhi,mid+1,r,plus);
    return x;
}
pair<int,int> query(node *cur,int qlo,int qhi,int lo,int hi,pair<int,int> carry={0,0}){
    if(lo>=qlo && hi<=qhi)return {cur->sum.first+carry.first,cur->sum.second+carry.second};
    if(lo>qhi || hi<qlo)return {0,0};
    carry.first+=cur->lazy.first;
    carry.second+=cur->lazy.second;
    int mid=(lo+hi)/2;
    pair<int,int> x=query(cur->l,qlo,qhi,lo,mid,carry);
    pair<int,int> y=query(cur->r,qlo,qhi,mid+1,hi,carry);
    x.first+=y.first; x.second+=y.second;
    return x;
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,m,q; cin>>n>>m>>q;
    for(int i=0;i<n-1;i++){
        int x,y; cin>>x>>y;
        road[i]={x,y};
        adj[x].pb(y); adj[y].pb(x);
    }
    for(int i=0;i<m;i++){
        int id,cost; cin>>id>>cost; id--;
        p[i]={cost,id};
        c[road[id]]++;
        swap(road[id].first,road[id].second);
        c[road[id]]++;
    }
    sort(p,p+m);
    dfs(1,0,0);
    while(offset<=tim)offset*=2;
    root[0]=new node;
    build(root[0],0,offset-1);
    for(int i=0;i<m;i++){
        int x=road[p[i].second].first,y=road[p[i].second].second;
        if(tin[y]>tin[x])x=y;
        root[i+1]=insert(root[i],tin[x],tout[x],0,offset-1,p[i].first);
    }
    while(q--){
        int s,t,x,y; cin>>s>>t>>x>>y;
        int lc=lca(s,t);
        int l=0,r=m;
        while(l<r){
            int mid=(l+r+1)/2; //all edges with silver<p[mid].first we will pay with silver otherwise gold.
            pair<int,int> a=query(root[mid],tin[s],tin[s],0,offset-1);
            pair<int,int> b=query(root[mid],tin[t],tin[t],0,offset-1);
            pair<int,int> e=query(root[mid],tin[lc],tin[lc],0,offset-1);
            int silv=a.first+b.first-e.first*2;
            if(silv<=y)l=mid;
            else r=mid-1;
        //    cout<<l<<' '<<r<<' '<<mid<<' '<<silv<<endl;
        }
        int mid=l;
        pair<int,int> a=query(root[mid],tin[s],tin[s],0,offset-1);
        pair<int,int> b=query(root[mid],tin[t],tin[t],0,offset-1);
        pair<int,int> e=query(root[mid],tin[lc],tin[lc],0,offset-1);
        int silv=a.first+b.first-e.first*2;
        int gld=a.second+b.second-e.second*2;
        //cout<<l<<' '<<lc<<' '<<gld<<' '<<silv<<' '<<e.first<<' '<<e.second<<endl;
        if(gld<=x && silv<=y)cout<<x-gld<<endl;
        else cout<<-1<<endl;
    }
}
/*
7 6 1
1 2
1 3
2 4
2 5
3 6
3 7
1 1
2 2
3 3
4 4
5 5
6 6
6 4 3 3
*/

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