#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 = 100005;
vi g[N];
pii p[N];
map<pii, vi> mp;
int t;
int pre[N];
void dfs(int pos, int pr){
if(pos == t)return;
for(auto to:g[pos]){
if(to!=pr){
pre[to] = pos;
dfs(to, pos);
}
}
}
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});
}
for(int i = 0; i < m; i++){
int j, c;
cin >> j >> c;j--;
mp[cui[j]].pb(c);
mp[{cui[j].ss, cui[j].ff}].pb(c);
}
if(n >= 2006){
dfs(1, -1);
vi pas;
while(q--){
int s, x, y;
cin >> s >> t >> x >> y;
if(s > t)swap(s, t);
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{
vi pas;
while(q--){
int s, x, y;
cin >> s >> t >> x >> y;
dfs(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';
}
}
}
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:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
91 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4952 KB |
Output is correct |
2 |
Correct |
1 ms |
4956 KB |
Output is correct |
3 |
Correct |
1 ms |
4952 KB |
Output is correct |
4 |
Correct |
2 ms |
4956 KB |
Output is correct |
5 |
Correct |
29 ms |
5488 KB |
Output is correct |
6 |
Correct |
45 ms |
5444 KB |
Output is correct |
7 |
Correct |
24 ms |
5212 KB |
Output is correct |
8 |
Correct |
46 ms |
5468 KB |
Output is correct |
9 |
Correct |
46 ms |
5560 KB |
Output is correct |
10 |
Correct |
46 ms |
5468 KB |
Output is correct |
11 |
Correct |
48 ms |
5464 KB |
Output is correct |
12 |
Correct |
48 ms |
5468 KB |
Output is correct |
13 |
Correct |
222 ms |
5636 KB |
Output is correct |
14 |
Correct |
227 ms |
5644 KB |
Output is correct |
15 |
Correct |
123 ms |
5464 KB |
Output is correct |
16 |
Correct |
114 ms |
5468 KB |
Output is correct |
17 |
Correct |
94 ms |
5580 KB |
Output is correct |
18 |
Correct |
125 ms |
5596 KB |
Output is correct |
19 |
Correct |
18 ms |
5468 KB |
Output is correct |
20 |
Correct |
17 ms |
5468 KB |
Output is correct |
21 |
Correct |
18 ms |
5544 KB |
Output is correct |
22 |
Correct |
18 ms |
5720 KB |
Output is correct |
23 |
Correct |
83 ms |
5408 KB |
Output is correct |
24 |
Correct |
96 ms |
5464 KB |
Output is correct |
25 |
Correct |
80 ms |
5468 KB |
Output is correct |
26 |
Correct |
25 ms |
5464 KB |
Output is correct |
27 |
Correct |
25 ms |
5468 KB |
Output is correct |
28 |
Correct |
28 ms |
5716 KB |
Output is correct |
29 |
Correct |
28 ms |
5468 KB |
Output is correct |
30 |
Correct |
45 ms |
5468 KB |
Output is correct |
31 |
Correct |
45 ms |
5548 KB |
Output is correct |
32 |
Correct |
45 ms |
5544 KB |
Output is correct |
33 |
Correct |
143 ms |
5636 KB |
Output is correct |
34 |
Correct |
146 ms |
5660 KB |
Output is correct |
35 |
Correct |
146 ms |
5464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4952 KB |
Output is correct |
2 |
Correct |
46 ms |
5460 KB |
Output is correct |
3 |
Correct |
45 ms |
5468 KB |
Output is correct |
4 |
Correct |
47 ms |
5436 KB |
Output is correct |
5 |
Execution timed out |
5019 ms |
23472 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4952 KB |
Output is correct |
2 |
Correct |
144 ms |
5544 KB |
Output is correct |
3 |
Correct |
145 ms |
5468 KB |
Output is correct |
4 |
Correct |
150 ms |
5644 KB |
Output is correct |
5 |
Execution timed out |
5054 ms |
29512 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4952 KB |
Output is correct |
2 |
Correct |
1 ms |
4956 KB |
Output is correct |
3 |
Correct |
1 ms |
4952 KB |
Output is correct |
4 |
Correct |
2 ms |
4956 KB |
Output is correct |
5 |
Correct |
29 ms |
5488 KB |
Output is correct |
6 |
Correct |
45 ms |
5444 KB |
Output is correct |
7 |
Correct |
24 ms |
5212 KB |
Output is correct |
8 |
Correct |
46 ms |
5468 KB |
Output is correct |
9 |
Correct |
46 ms |
5560 KB |
Output is correct |
10 |
Correct |
46 ms |
5468 KB |
Output is correct |
11 |
Correct |
48 ms |
5464 KB |
Output is correct |
12 |
Correct |
48 ms |
5468 KB |
Output is correct |
13 |
Correct |
222 ms |
5636 KB |
Output is correct |
14 |
Correct |
227 ms |
5644 KB |
Output is correct |
15 |
Correct |
123 ms |
5464 KB |
Output is correct |
16 |
Correct |
114 ms |
5468 KB |
Output is correct |
17 |
Correct |
94 ms |
5580 KB |
Output is correct |
18 |
Correct |
125 ms |
5596 KB |
Output is correct |
19 |
Correct |
18 ms |
5468 KB |
Output is correct |
20 |
Correct |
17 ms |
5468 KB |
Output is correct |
21 |
Correct |
18 ms |
5544 KB |
Output is correct |
22 |
Correct |
18 ms |
5720 KB |
Output is correct |
23 |
Correct |
83 ms |
5408 KB |
Output is correct |
24 |
Correct |
96 ms |
5464 KB |
Output is correct |
25 |
Correct |
80 ms |
5468 KB |
Output is correct |
26 |
Correct |
25 ms |
5464 KB |
Output is correct |
27 |
Correct |
25 ms |
5468 KB |
Output is correct |
28 |
Correct |
28 ms |
5716 KB |
Output is correct |
29 |
Correct |
28 ms |
5468 KB |
Output is correct |
30 |
Correct |
45 ms |
5468 KB |
Output is correct |
31 |
Correct |
45 ms |
5548 KB |
Output is correct |
32 |
Correct |
45 ms |
5544 KB |
Output is correct |
33 |
Correct |
143 ms |
5636 KB |
Output is correct |
34 |
Correct |
146 ms |
5660 KB |
Output is correct |
35 |
Correct |
146 ms |
5464 KB |
Output is correct |
36 |
Correct |
1 ms |
4952 KB |
Output is correct |
37 |
Correct |
46 ms |
5460 KB |
Output is correct |
38 |
Correct |
45 ms |
5468 KB |
Output is correct |
39 |
Correct |
47 ms |
5436 KB |
Output is correct |
40 |
Execution timed out |
5019 ms |
23472 KB |
Time limit exceeded |
41 |
Halted |
0 ms |
0 KB |
- |