#include <bits/stdc++.h>
using namespace std;/*
<<<<It's never too late for a new beginning in your life>>>>
Today is hard
tomorrow will worse
but the day after tomorrow will be the sunshine..
HARD WORK BEATS TALENT WHEN TALENT DOESN'T WORK HARD............
Never give up */
//The most CHALISHKANCHIK
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vii;
const int N = 1e5+5;
vi g[N];
map<pii, vi> mp;
int pre[N];
int n, q, timer;
int tin[N], tout[N];
int up[20][N];
int num[N]{};
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];
}
void sukfe(int v, int pr){
for (int to : g[v]) {
if (to == pr) continue;
num[to] = num[v];
num[to] += mp[{v, to}].size();
dfs(to, v);
}
}
void dfs2(int v, int pr){
for (int to : g[v]) {
if (to == pr) continue;
pre[to] = v;
dfs2(to, v);
}
}
void solve(){
int n, m, q;
cin >> n >> m >> q;
vii cui;
for(int i = 0; i < n-1; i++){
int a, b;
cin >> a >> b;
g[a].pb(b);
g[b].pb(a);
cui.pb({a, b});
}
int j, c;
set<int> st;
for(int i = 0; i < m; i++){
cin >> j >> c;
j--;
mp[cui[j]].pb(c);
mp[{cui[j].ss, cui[j].ff}].pb(c);
st.insert(c);
}
if(st.size()>1){
vi pas;
while(q--){
int s, t, x, y;
cin >> s >> t >> x >> y;
dfs2(s, -1);
int r = t;
while(r!=s){
for(auto i:mp[{r, pre[r]}])pas.pb(i);
r = pre[r];
}
sort(all(pas));
for(auto i:pas){
if(i <= y)y -= i;
else x--;
}pas.clear();
cout << (x < 0 ? -1 : x) << '\n';
}
}else{
dfs(1, -1);
sukfe(1, -1);
while(q--){
int a, b, x, y;
cin >> a >> b >> x >> y;
int cnt = num[a] + num[b];
int lc = lca(a, b);
cnt -= num[lc] * 2;
int ans = y/c;
cnt -= ans;
if(x - cnt < 0)cout << -1 << '\n';
else cout << x - cnt << '\n';
}
}
}
main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t = 1;
//~ cin >> t;
while(t--){
solve();
}
}
Compilation message
currencies.cpp:127:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
127 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
19292 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
19292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4952 KB |
Output is correct |
| 2 |
Correct |
155 ms |
5648 KB |
Output is correct |
| 3 |
Correct |
156 ms |
5464 KB |
Output is correct |
| 4 |
Correct |
157 ms |
5648 KB |
Output is correct |
| 5 |
Execution timed out |
5043 ms |
33932 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
19292 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
