Submission #888824

#	Time	Username	Problem	Language	Result	Execution time	Memory
888824		vjudge1	Two Currencies (JOI23_currencies)	C++17	38 / 100	510 ms	63300 KiB

currencies

 #include <bits/stdc++.h> 
 #include <ext/pb_ds/assoc_container.hpp> 
 #include <ext/pb_ds/tree_policy.hpp> 
 #pragma GCC target("avx,avx2,fma") 
 #pragma GCC optimize("Ofast,unroll-loops") 
 #define pii pair<int,int> 
 using namespace __gnu_pbds; 
 using namespace std; 
 #define pb push_back 
 #define all(x) x.begin(),x.end() 
 #define rall(x) x.rbegin(),x.rend() 
 #define int long long 
 #define f first 
 #define s second 
 #define pii pair<int,int> 
 template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;} 
 template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;} 
 typedef tree<int, null_type, less_equal<int>, rb_tree_tag, 
  tree_order_statistics_node_update> ordered_set; 
 const int mod= 1e9 +7; 
 const int N = 1e5 + 6; 
  
 int n, q, timer, m; 
 int tin[N], tout[N],cnt[N],prad[N]; 
 map<pii,int>mp; 
 map<pii,vector<int>>cost; 
 int up[20][N]; 
 vector <int> g[N]; 
 //----------------------------------------------------------------------1------------------------------------------------- 
 //------------------lca-------------------- 
 void dfs(int v, int pr) { 
     tin[v] = ++timer; 
     up[0][v] = pr; 
     for (int i = 1; i <= 17; i++) { 
         up[i][v] = up[i - 1][ up[i - 1][v] ]; 
     } 
     for (int to : g[v]) { 
         if (to == pr) continue; 
         dfs(to, v); 
     } 
     tout[v] = timer; 
 } 
  
 bool upper(int a, int b) { 
     return tin[a] <= tin[b] && tout[a] >= tout[b]; 
 } 
  
 int lca(int a, int b) { 
     if (upper(a, b)) return a; 
     if (upper(b, a)) return b; 
     for (int i = 17; i >= 0; i--) { 
         if (!upper(up[i][a], b)) { 
             a = up[i][a]; 
         } 
     } 
     return up[0][a]; 
 } 
 //-------------------cnt of marked-------------- 
 void mark(int x,int pr){ 
  
  for(auto to:g[x]){ 
   if(to==pr)continue; 
   cnt[to] = cnt[x]; 
   cnt[to] += mp[{x,to}]; 
   mark(to,x); 
  } 
   
 } 
 //---------------------------------------------------------------------------------------------------------------- 
 //-------------------------kolhoz----------- 
 void dfs1(int x,int pr){ 
   
  for(auto to:g[x]){ 
 //  cout<<to<<" "; 
   if(to==pr)continue; 
   prad[to] = x; 
   dfs1(to,x); 
  } 
   
 } 
 
  
  
 void solve(){ 
     cin >> n >> m >> q; 
      
  vector<pii>v; 
     for (int i = 1; i < n; i++) { 
         int u, o; 
         cin >> u >> o; 
         g[u].push_back(o); 
         g[o].push_back(u); 
         v.pb({u,o}); 
     } 
     int val = 0; 
     map<int,int>mps; 
     bool flag = false; 
  for(int i = 0; i < m; i++){ 
   int j,k; 
   cin>>j>>k; 
   pii l = v[j-1]; 
   mp[{l.f,l.s}]++; 
   mp[{l.s,l.f}]++; 
   cost[{l.f,l.s}].pb(k); 
   cost[{l.s,l.f}].pb(k); 
   val = k; 
   mps[k]++; 
   if(mps[k]==1&&i>0)flag = true; 
  } 
  
  if(!flag){ 
   ////----------------------28--------------------- 
      dfs(1, 1); 
      mark(1,-1); 
       
      while (q--) { 
          int u, v; 
          int sum,gold; 
          cin >> u >> v >> gold >> sum; 
          int h = lca(u, v);
          int ans = cnt[u] + cnt[v]; 
          ans -= cnt[h] * 2; 
           
          int l = 1,r = ans,ans1 = 0; 
          while(l<=r){ 
           int mid = (l+r)/2; 
           if(mid*val>sum){ 
            r = mid - 1; 
     } 
     else { 
      ans1 = mid; 
      l = mid + 1; 
     } 
    } 
    ans -= ans1; 
    if(gold-ans<0)cout<<-1<<"\n"; 
    else cout<<gold - ans<<"\n"; 
           
      } 
    
  } 
  else{ 
   //-----------------------------10----------------------------- 
   if(n<=2000){ 
    while(q--){ 
     int a,b,c,d; 
     cin>>a>>b>>c>>d; 
     dfs1(a,-1); 
     vector<int>ans; 
      
     while(b!=a){ 
      for(auto to:cost[{b,prad[b]}])ans.pb(to); 
      b = prad[b]; 
     } 
     sort(all(ans)); 
     for(int i = 0;i<(int)ans.size();i++){ 
      if(d - ans[i]<0){ 
       int u = ans.size() - i; 
       c = max(c - u, 0ll-1ll); 
       break; 
      } 
      d -= ans[i]; 
     } 
     cout<<c<<"\n"; 
      
    }  
   } 
   else{ 
     
     
     
   } 
    
  } 
  
 } 
  
 signed main() { 
  ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); 
  int tt = 1; 
  while(tt--){ 
   solve(); 
  } 
   
   
 }

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