#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
template<typename T>
int len(T &a){
return a.size();
}
void solve(){
int n, m, q; cin >> n >> m >> q;
vector<vector<pair<int,int>>> g(n);
for(int i = 0; i < n - 1; i ++){
int u, v; cin >> u >> v;
u --; v --;
g[u].push_back({v, i});
g[v].push_back({u, i});
}
vector<vector<int>> way(n - 1);
for(int i = 0; i < m; i ++){
int id, sil; cin >> id >> sil;
id --; way[id].push_back(sil);
}
vector<int> st(q), en(q), gold(q);
vector<ll> silver(q);
for(int i = 0; i < q; i ++){
cin >> st[i] >> en[i] >> gold[i] >> silver[i];
st[i] --; en[i] --;
}
auto brute = [&]{
vector<int> par(n), wayid(n);
auto dfs = [&](auto &dfs, int i, int p = -1, int r = -1)->void{
par[i] = p;
wayid[i] = r;
for(auto [u, id] : g[i]){
if(u == p) continue;
dfs(dfs, u, i, id);
}
};
for(int i = 0; i < q; i ++){
dfs(dfs, st[i]);
vector<ll> pay;
int cur = en[i];
while(wayid[cur] != -1){
//cout << wayid[cur] + 1 << ' ';
for(auto u : way[wayid[cur]]){
pay.push_back(u);
//cout << u << ' ';
}
cur = par[cur];
}
if(pay.empty()){
cout << gold[i] << '\n'; continue;
}
sort(all(pay));
for(int j = 1; j < len(pay); j ++){
pay[j] += pay[j - 1];
}
int rem = gold[i] - len(pay) + (upper_bound(all(pay), silver[i]) - pay.begin());
cout << max(-1, rem) << '\n';
}
};
brute();
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int testcases = 1;
#ifdef Tests
cin >> testcases;
#endif
while(testcases --){
solve();
if(testcases) cout << '\n';
#ifdef LOCAL
else
cout << '\n';
cout << "________________________" << endl;
#endif
}
#ifdef LOCAL
cout << "done" << endl;
#endif
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
26 ms |
680 KB |
Output is correct |
6 |
Correct |
43 ms |
660 KB |
Output is correct |
7 |
Correct |
22 ms |
600 KB |
Output is correct |
8 |
Correct |
46 ms |
784 KB |
Output is correct |
9 |
Correct |
47 ms |
604 KB |
Output is correct |
10 |
Correct |
47 ms |
604 KB |
Output is correct |
11 |
Correct |
47 ms |
600 KB |
Output is correct |
12 |
Correct |
49 ms |
792 KB |
Output is correct |
13 |
Correct |
139 ms |
860 KB |
Output is correct |
14 |
Correct |
139 ms |
856 KB |
Output is correct |
15 |
Correct |
87 ms |
604 KB |
Output is correct |
16 |
Correct |
81 ms |
804 KB |
Output is correct |
17 |
Correct |
75 ms |
816 KB |
Output is correct |
18 |
Correct |
91 ms |
604 KB |
Output is correct |
19 |
Correct |
21 ms |
604 KB |
Output is correct |
20 |
Correct |
29 ms |
604 KB |
Output is correct |
21 |
Correct |
26 ms |
600 KB |
Output is correct |
22 |
Correct |
28 ms |
784 KB |
Output is correct |
23 |
Correct |
100 ms |
808 KB |
Output is correct |
24 |
Correct |
86 ms |
600 KB |
Output is correct |
25 |
Correct |
87 ms |
604 KB |
Output is correct |
26 |
Correct |
30 ms |
600 KB |
Output is correct |
27 |
Correct |
29 ms |
604 KB |
Output is correct |
28 |
Correct |
32 ms |
604 KB |
Output is correct |
29 |
Correct |
33 ms |
604 KB |
Output is correct |
30 |
Correct |
48 ms |
604 KB |
Output is correct |
31 |
Correct |
46 ms |
728 KB |
Output is correct |
32 |
Correct |
47 ms |
796 KB |
Output is correct |
33 |
Correct |
93 ms |
860 KB |
Output is correct |
34 |
Correct |
100 ms |
860 KB |
Output is correct |
35 |
Correct |
99 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
48 ms |
720 KB |
Output is correct |
3 |
Correct |
50 ms |
788 KB |
Output is correct |
4 |
Correct |
46 ms |
792 KB |
Output is correct |
5 |
Execution timed out |
5057 ms |
17060 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
95 ms |
604 KB |
Output is correct |
3 |
Correct |
90 ms |
856 KB |
Output is correct |
4 |
Correct |
92 ms |
860 KB |
Output is correct |
5 |
Execution timed out |
5085 ms |
19100 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
26 ms |
680 KB |
Output is correct |
6 |
Correct |
43 ms |
660 KB |
Output is correct |
7 |
Correct |
22 ms |
600 KB |
Output is correct |
8 |
Correct |
46 ms |
784 KB |
Output is correct |
9 |
Correct |
47 ms |
604 KB |
Output is correct |
10 |
Correct |
47 ms |
604 KB |
Output is correct |
11 |
Correct |
47 ms |
600 KB |
Output is correct |
12 |
Correct |
49 ms |
792 KB |
Output is correct |
13 |
Correct |
139 ms |
860 KB |
Output is correct |
14 |
Correct |
139 ms |
856 KB |
Output is correct |
15 |
Correct |
87 ms |
604 KB |
Output is correct |
16 |
Correct |
81 ms |
804 KB |
Output is correct |
17 |
Correct |
75 ms |
816 KB |
Output is correct |
18 |
Correct |
91 ms |
604 KB |
Output is correct |
19 |
Correct |
21 ms |
604 KB |
Output is correct |
20 |
Correct |
29 ms |
604 KB |
Output is correct |
21 |
Correct |
26 ms |
600 KB |
Output is correct |
22 |
Correct |
28 ms |
784 KB |
Output is correct |
23 |
Correct |
100 ms |
808 KB |
Output is correct |
24 |
Correct |
86 ms |
600 KB |
Output is correct |
25 |
Correct |
87 ms |
604 KB |
Output is correct |
26 |
Correct |
30 ms |
600 KB |
Output is correct |
27 |
Correct |
29 ms |
604 KB |
Output is correct |
28 |
Correct |
32 ms |
604 KB |
Output is correct |
29 |
Correct |
33 ms |
604 KB |
Output is correct |
30 |
Correct |
48 ms |
604 KB |
Output is correct |
31 |
Correct |
46 ms |
728 KB |
Output is correct |
32 |
Correct |
47 ms |
796 KB |
Output is correct |
33 |
Correct |
93 ms |
860 KB |
Output is correct |
34 |
Correct |
100 ms |
860 KB |
Output is correct |
35 |
Correct |
99 ms |
860 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
48 ms |
720 KB |
Output is correct |
38 |
Correct |
50 ms |
788 KB |
Output is correct |
39 |
Correct |
46 ms |
792 KB |
Output is correct |
40 |
Execution timed out |
5057 ms |
17060 KB |
Time limit exceeded |
41 |
Halted |
0 ms |
0 KB |
- |