| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 888622 | vjudge1 | Two Currencies (JOI23_currencies) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
//------------------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-----------------------------
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<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";
}
}
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int tt = 1;
while(tt--){
solve();
}
}