#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
vector<vector<int>> ddj;
vector<vector<int>> rdj;
vector<vector<int>> roads;
vector<vector<int>> che;
int solve(int s, int t, int x, int y, int n){
// road, node, parent
queue<vector<int>> q;
q.push({-1, s, -1});
vector<int> v(n, 0);
vector<int> parents(n, 0);
vector<int> ru(n, 0);
parents[s] = -1;
int node; int road; int parent;
while(!q.empty()){
node = q.front()[1]; road = q.front()[0]; parent = q.front()[2];
q.pop();
if(!v[node]){
parents[node] = parent;
ru[node] = road;
v[node] = 1;
for(int i = 0; i < adj[node].size(); i ++){
q.push({rdj[node][i], adj[node][i], node});
}
}
}
vector<int> coins;
//cout << " | ";
node = t;
while(parents[node] != -1){
for(int i = 0; i < che[ru[node]].size(); i ++){
coins.push_back(che[ru[node]][i]);
}
//cout << ru[node] << " ";
node = parents[node];
} //cout << " | ";
sort(coins.begin(), coins.end());
//cout << " | ";
for(int i = 0; i < coins.size(); i ++){
if(y - coins[i] >= 0){
y -= coins[i];
} else {
x -= 1;
}
//cout << coins[i] << " ";
}
if(x >= 0){
return x;
} else {
return -1;
}
//cout << " | ";
}
int main(){
int n, m, queries; cin >> n >> m >> queries;
vector<vector<int>> adj0(n, vector<int>());
vector<vector<int>> ddj0(n, vector<int>());
vector<vector<int>> rdj0(n, vector<int>());
vector<vector<int>> roads;
int a, b, p, c;
for(int i = 0; i < n - 1; i ++){
cin >> a >> b; a -= 1; b -= 1;
roads.push_back({a, b});
}
vector<vector<int>> checkpoints(n-1, vector<int>());
for(int i = 0; i < m; i ++){
cin >> p >> c;
p -= 1;
checkpoints[p].push_back(c);
}
for(int i = 0; i < roads.size(); i ++){
adj0[roads[i][0]].push_back(roads[i][1]); adj0[roads[i][1]].push_back(roads[i][0]);
ddj0[roads[i][0]].push_back(roads[i][2]); ddj0[roads[i][1]].push_back(roads[i][2]);
rdj0[roads[i][0]].push_back(i); rdj0[roads[i][1]].push_back(i);
}
adj = adj0; ddj = ddj0; rdj = rdj0; che = checkpoints;
// start, end, gold, silver
int s, t, x, y;
vector<int> res;
for(int i = 0; i < queries; i ++){
cin >> s >> t >> x >> y;
s -= 1; t -= 1;
res.push_back(solve(s, t, x, y, n));
}
for(int i = 0; i < res.size(); i ++){
cout << res[i] << "\n";
}
}
/*
g++ -std=gnu++17 -O2 -pipe -o 7 7.cpp
5 4 3
1 2
1 3
2 4
2 5
2 9
2 4
3 5
4 7
3 4 2 11
5 3 4 5
2 3 1 1
*/
Compilation message
currencies.cpp: In function 'int solve(int, int, int, int, int)':
currencies.cpp:24:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(int i = 0; i < adj[node].size(); i ++){
| ~~^~~~~~~~~~~~~~~~~~
currencies.cpp:33:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int i = 0; i < che[ru[node]].size(); i ++){
| ~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int i = 0; i < coins.size(); i ++){
| ~~^~~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i = 0; i < roads.size(); i ++){
| ~~^~~~~~~~~~~~~~
currencies.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i = 0; i < res.size(); i ++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Runtime error |
1442 ms |
1048576 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
94 ms |
2528 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
55 ms |
2448 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Runtime error |
1442 ms |
1048576 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
