Submission #1223053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223053		minhpk	Two Currencies (JOI23_currencies)	C++20	100 / 100	2322 ms	154044 KiB

currencies

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b,c;
vector <int> z[1000005];
pair<int,int> t[1000005];
bool cmp(pair<int,int> a ,pair<int,int> b){
     return a.second<b.second;
}

int logarit[1000005];
int sta[1000005];
int fin[1000005];

int euler[1000005];
int tour;
int high[1000005];
int st[300001][20];

int sta1[1000005];
int fin1[1000005];
int tour1;
void dfs(int i,int par){

    tour++;
    sta[i]=tour;
    euler[tour]=i;

    tour1++;
    sta1[i]=tour1;

    for (auto p:z[i]){
         if (p==par){
            continue;
         }
         high[p]=high[i]+1;
         dfs(p,i);
         tour++;
         euler[tour]=i;
    }

    tour++;
    euler[tour]=i;
    fin[i]=tour;

    fin1[i]=tour1;
}


void buildst(){
    for (int i=1;i<=tour;i++){
         st[i][0]=euler[i];
    }

    for (int j=1;j<=20;j++){
         for (int i=1;i+(1<<j)-1<=tour;i++){
              int l=st[i][j-1];
              int r=st[i+(1<<(j-1))][j-1];

              if (high[l]<high[r]){
                 st[i][j]=l;
              }else{
                 st[i][j]=r;
              }
         }
    }
}

int lca(int x,int y){
    int l = min(sta[x], sta[y]);
    int r = max(sta[x], sta[y]);
    int j = logarit[r - l + 1];
    int idx1 = st[l][j];
    int idx2 = st[r - (1 << j) + 1][j];
    return (high[idx1] < high[idx2] ? idx1 : idx2);
}

struct SegmentTree{
      int n;
      int tree[4000005];
      int lazy[4000005];

      void push(int id){
           if (lazy[id]!=0){
               lazy[id*2]+=lazy[id];
               lazy[id*2+1]+=lazy[id];


               tree[id*2]+=lazy[id];
               tree[id*2+1]+=lazy[id];

               lazy[id]=0;
           }
      }

      void build(int id,int l,int r){
           lazy[id]=0;
           tree[id]=0;
           if (l==r){
             return;
           }
           int mid=(l+r)/2;
           build(id*2,l,mid);
           build(id*2+1,mid+1,r);
      }


      void update(int id,int l,int r,int x,int y,int val){
           if (x>r ||y<l){
               return;
           }
           if (l>=x && y>=r){
               tree[id]+=val;
               lazy[id]+=val;
               return;
           }
           int mid=(l+r)/2;
           push(id);
           update(id*2,l,mid,x,y,val);
           update(id*2+1,mid+1,r,x,y,val);
           tree[id]=tree[id*2]+tree[id*2+1];
      }


      int get(int id,int l,int r,int pos){
          if (l==r){
              return tree[id];
          }
          int mid=(l+r)/2;
          push(id);
          if (pos<=mid){
             return get(id*2,l,mid,pos);
          }else{
             return get(id*2+1,mid+1,r,pos);
          }
      }

};

SegmentTree f;
SegmentTree f1;

struct query{
    int x,y,g,val;
};

query q[1000005];
vector<int> v[1000005];
int l[1000005];
int r[1000005];
int ans1[1000005];
int ans2[1000005];

pair<int,int> edge[1000005];

int calc(int x,int y){
    int idx1=f.get(1,1,tour1,sta1[x]);
    int idx2=f.get(1,1,tour1,sta1[y]);
    int idx3=2*f.get(1,1,tour1,sta1[lca(x,y)]);
    return idx1+idx2-idx3;
}

int calc1(int x,int y){
    int idx1=f1.get(1,1,tour1,sta1[x]);
    int idx2=f1.get(1,1,tour1,sta1[y]);
    int idx3=2*f1.get(1,1,tour1,sta1[lca(x,y)]);
    return idx1+idx2-idx3;
}

signed main()
{
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b >> c;
    for (int i=1;i<a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(y);
         z[y].push_back(x);
         edge[i]={x,y};
    }
    for (int i=1;i<=b;i++){
         cin >> t[i].first >> t[i].second;
    }

    logarit[2] = 1;
    for(int i = 3; i <= 1000000; i++){
         logarit[i] = logarit[i/2] + 1;
    }
    sort(t+1,t+1+b,cmp);
    dfs(1,0);
    buildst();

    for (int i=1;i<=c;i++){
         cin >> q[i].x >> q[i].y >> q[i].g >> q[i].val;
    }

    for (int i=1;i<=c;i++){
         ans1[i]=0;
         ans2[i]=0;
         l[i]=0;
         r[i]=b;
    }

    while (true){
         bool check=false;

         for (int i=1;i<=c;i++){
              if (l[i]<=r[i]){
                  check=true;
                  int mid=(l[i]+r[i])/2;
                  v[mid].push_back(i);
              }
         }

         if (!check){
            break;
         }

         f.build(1,1,tour1);
         f1.build(1,1,tour1);

         for (int i=0;i<=b;i++){
           if (i>0){
               auto [x,y]=edge[t[i].first];
              if (high[x]<high[y]){
                  swap(x,y);
              }
              f.update(1,1,tour1,sta1[x],fin1[x],t[i].second);
              f1.update(1,1,tour1,sta1[x],fin1[x],1);
           }

              for (auto p:v[i]){
                   int precal=calc(q[p].x,q[p].y);
                   if (q[p].val>=precal){
                       ans1[p]=i;
                       l[p]=i+1;
                       ans2[p]=calc1(q[p].x,q[p].y);
                   }else{
                       r[p]=i-1;
                   }
              }
              v[i].clear();
         }
    }

    f1.build(1,1,tour1);
    for (int i=1;i<=b;i++){
         auto [x,y]=edge[t[i].first];
         if (high[x]<high[y]){
             swap(x,y);
         }
       //  cout << x << " ";
         f1.update(1,1,tour1,sta1[x],fin1[x],1);
    }
   // cout << calc1(3,5) << "\n";
    for (int i=1;i<=c;i++){
         int val=calc1(q[i].x,q[i].y);
         int remain=val-ans2[i];
         remain=q[i].g-remain;
         if (remain>=0){
            cout << remain << "\n";
         }else{
            cout << -1 << "\n";
         }
    }


    return 0;
}
/*
5 4 1
1 2
1 3
2 4
2 5

2 9
2 4
3 5
4 7

5 3 4 5
*/






/*
5
10 9 3 6 1
3
2 1 2 4
1 2 4
1 2 2



5
2 8 6 4 1
4
3 1 2 9
1 1 3
2 1 4 5
1 2 5
*/





/*
8
01010101
10111000


8
01010101
10111000
10101010


6
110110
011101


001001


8
01010101
11000010

10101010
*/



/*
freopen("test.txt", "r", stdin);
    freopen("o2.out", "w", stdout);
*/

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