#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,lo=21;
int an[N][lo],dis[N],cost[N];
map<pair<int,int>,int>mp;
pair<int,int> ed[N];
vector<int> a[N];
void dfs(int x,int p)
{
an[x][0]=p;
dis[x]=dis[p]+1;
cost[x]=mp[{x,p}]+cost[p];
for(int i=1;i<lo;i++) an[x][i]=an[an[x][i-1]][i-1];
for(auto i:a[x]) if(i!=p) dfs(i,x);
}
int lca(int x,int y)
{
if(dis[x]>dis[y]) swap(x,y);
for(int i=lo-1;i>=0;i--)
if(dis[an[y][i]]>=dis[x]) y=an[y][i];
if(x==y) return x;
for(int i=lo-1;i>=0;i--)
if(an[x][i]!=an[y][i])
x=an[x][i],y=an[y][i];
return an[x][0];
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,m,q; cin>>n>>m>>q;
for(int i=1;i<n;i++)
{
int u,v; cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
ed[i]={u,v};
}
int val;
for(int i=0;i<m;i++)
{
int p; cin>>p>>val;
auto [f,s]=ed[p];
mp[{f,s}]++;
mp[{s,f}]++;
}
dis[0]=-1; dfs(1,0);
while(q--)
{
int x,y,g,s; cin>>x>>y>>g>>s;
int node=lca(x,y);
int ss=cost[x]+cost[y]-2*cost[node];
ss-=(int)(s/val); ss=max(ss,0ll);
g-=ss;
if(g<0) cout<<-1<<endl;
else cout<<g<<endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
6748 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6748 KB |
Output is correct |
2 |
Correct |
6 ms |
7172 KB |
Output is correct |
3 |
Correct |
6 ms |
7004 KB |
Output is correct |
4 |
Correct |
6 ms |
7004 KB |
Output is correct |
5 |
Correct |
305 ms |
40120 KB |
Output is correct |
6 |
Correct |
282 ms |
31012 KB |
Output is correct |
7 |
Correct |
293 ms |
36324 KB |
Output is correct |
8 |
Correct |
244 ms |
36176 KB |
Output is correct |
9 |
Correct |
248 ms |
36308 KB |
Output is correct |
10 |
Correct |
397 ms |
41176 KB |
Output is correct |
11 |
Correct |
364 ms |
40932 KB |
Output is correct |
12 |
Correct |
359 ms |
40768 KB |
Output is correct |
13 |
Correct |
364 ms |
40824 KB |
Output is correct |
14 |
Correct |
379 ms |
40784 KB |
Output is correct |
15 |
Correct |
464 ms |
50180 KB |
Output is correct |
16 |
Correct |
415 ms |
51152 KB |
Output is correct |
17 |
Correct |
430 ms |
49920 KB |
Output is correct |
18 |
Correct |
376 ms |
41560 KB |
Output is correct |
19 |
Correct |
391 ms |
41552 KB |
Output is correct |
20 |
Correct |
461 ms |
41816 KB |
Output is correct |
21 |
Correct |
321 ms |
41160 KB |
Output is correct |
22 |
Correct |
320 ms |
41560 KB |
Output is correct |
23 |
Correct |
309 ms |
41408 KB |
Output is correct |
24 |
Correct |
313 ms |
41216 KB |
Output is correct |
25 |
Correct |
358 ms |
40528 KB |
Output is correct |
26 |
Correct |
316 ms |
40684 KB |
Output is correct |
27 |
Correct |
308 ms |
40532 KB |
Output is correct |
28 |
Correct |
323 ms |
41464 KB |
Output is correct |
29 |
Correct |
327 ms |
41516 KB |
Output is correct |
30 |
Correct |
344 ms |
41964 KB |
Output is correct |
31 |
Correct |
328 ms |
41824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
6744 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
6748 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |