Submission #729854

#	Time	Username	Problem	Language	Result	Execution time	Memory
729854		NemanjaSo2005	Two Currencies (JOI23_currencies)	C++14	100 / 100	3178 ms	47152 KiB

currencies

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N,M,Q,dub[100005],rod[20][100005],in[100005],out[100005],vrem=0;
struct grana{
   int c1,c2;
} grane[100005];
struct stan{
   ll gde,cena;
} stanica[100005];
bool cmp(stan a,stan b){
   return a.cena<b.cena;
}
struct upit{
   ll novca,zlato;
   int dg,gg,res,a,b;
} upiti[100005];
vector<int> stablo[100005],bucket[100005];
void dfs(int gde,int pret){
   rod[0][gde]=pret;
   in[gde]=++vrem;
   dub[gde]=dub[pret]+1;
   for(int i=0;i<stablo[gde].size();i++){
      if(stablo[gde][i]==pret)
         continue;
      dfs(stablo[gde][i],gde);
   }
   out[gde]=vrem;
   return;
}
ll flosih[100005],fcena[100005];
void lupdate(int gde,ll kol){
   for(int i=gde;i<=N;i+=(i)&(-i))
      flosih[i]+=kol;
   return;
}
void cupdate(int gde,ll kol){
   for(int i=gde;i<=N;i+=(i)&(-i))
      fcena[i]+=kol;
   return;
}
ll lget(int gde){
   ll ret=0;
   for(int i=gde;i>=1;i-=(i)&(-i))
      ret+=flosih[i];
   return ret;
}
ll cget(int gde){
   ll ret=0;
   for(int i=gde;i>=1;i-=(i)&(-i))
      ret+=fcena[i];
   return ret;
}
void aktiviraj(int koga){
   int a=in[stanica[koga].gde];
   int b=out[stanica[koga].gde];
   lupdate(a,-1);
   lupdate(b+1,1);
   cupdate(a,stanica[koga].cena);
   cupdate(b+1,-stanica[koga].cena);
   return;
}
bool isparent(int a,int b){
   return in[a]<=in[b] and out[a]>=out[b];
}
int LCA(int a,int b){
   if(isparent(a,b))
      return a;
   if(isparent(b,a))
      return b;
   for(int i=17;i>=0;i--)
      if(!isparent(rod[i][a],b))
         a=rod[i][a];
   return rod[0][a];
}
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cin>>N>>M>>Q;
   for(int i=1;i<N;i++){
      cin>>grane[i].c1>>grane[i].c2;
      stablo[grane[i].c1].push_back(grane[i].c2);
      stablo[grane[i].c2].push_back(grane[i].c1);
   }
   dfs(1,1);
   for(int j=1;j<=18;j++)
      for(int i=1;i<=N;i++)
         rod[j][i]=rod[j-1][rod[j-1][i]];
   for(int i=1;i<=M;i++){
      cin>>stanica[i].gde>>stanica[i].cena;
      int a=grane[stanica[i].gde].c1;
      int b=grane[stanica[i].gde].c2;
      if(dub[a]>dub[b])
         stanica[i].gde=a;
      else
         stanica[i].gde=b;
   }
   sort(stanica+1,stanica+1+M,cmp);
   for(int i=1;i<=Q;i++){
      cin>>upiti[i].a>>upiti[i].b>>upiti[i].zlato>>upiti[i].novca;
      upiti[i].dg=0;
      upiti[i].gg=M;
   }
   bool nastavi=true;
   while(nastavi){
      nastavi=false;
      for(int i=1;i<=Q;i++){
         if(upiti[i].gg<upiti[i].dg)
            continue;
        // cout<<upiti[i].dg<<" "<<upiti[i].gg<<endl;
         nastavi=true;
         bucket[(upiti[i].dg+upiti[i].gg)/2].push_back(i);
      }
      if(!nastavi)
         break;
      for(int i=1;i<=N;i++){
         flosih[i]=0;
         fcena[i]=0;
      }
      for(int i=1;i<=M;i++){
         int a=in[stanica[i].gde];
         int b=out[stanica[i].gde];
         lupdate(a,1);
         lupdate(b+1,-1);
      }
      for(int sred=0;sred<=M;sred++){
         if(sred!=0)
            aktiviraj(sred);
         for(int i=0;i<bucket[sred].size();i++){
            int koji=bucket[sred][i];
            int lc=LCA(upiti[koji].a,upiti[koji].b);
            ll c=cget(in[upiti[koji].a])+cget(in[upiti[koji].b])-2*cget(in[lc]);
            ll z=lget(in[upiti[koji].a])+lget(in[upiti[koji].b])-2*lget(in[lc]);
          //  cout<<c<<" "<<z<<endl;
            if(c<=upiti[koji].novca){
               upiti[koji].res=z;
               upiti[koji].dg=sred+1;
            }
            else
               upiti[koji].gg=sred-1;
         }
         bucket[sred].clear();
      }
   }
   for(int i=1;i<=Q;i++){
      if(upiti[i].zlato<upiti[i].res)
         cout<<"-1\n";
      else
         cout<<upiti[i].zlato-upiti[i].res<<"\n";
   }
   return 0;
}
/*
8 7 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 4
3 7
2 10
5 2
4 1
4 4
5 6
6 3 7 69
*/

Compilation message (stderr)

currencies.cpp: In function 'void dfs(int, int)':
currencies.cpp:23:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |    for(int i=0;i<stablo[gde].size();i++){
      |                ~^~~~~~~~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |          for(int i=0;i<bucket[sred].size();i++){
      |                      ~^~~~~~~~~~~~~~~~~~~~

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