QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#269482 | #6332. Two Currencies | paul2008# | 0 | 187ms | 124348kb | C++14 | 2.3kb | 2023-11-29 17:34:39 | 2024-07-04 03:11:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node
{
int lc,rc,sz,sum;
};
const int N=1e5+5;
node res[N*35];
vector <int> g[N],vec[N];
int x[N],y[N],fa[N][25],dep[N],rt[N],cnt;
void dfs1(int x)
{
for(int i=1;i<20;i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(auto to:g[x])
if(to!=fa[x][0])
dep[to]=dep[x]+1, fa[to][0]=x, dfs1(to);
}
int update(int x,int l,int r,int y)
{
int rt=++cnt;
res[rt]=res[x], res[rt].sz++, res[rt].sum += y;
if(l==r)
return rt;
int mid=(l+r)/2;
if(y<mid)
res[rt].lc=update(res[x].lc,l,mid,y);
else
res[rt].rc=update(res[x].rc,mid+1,r,y);
return rt;
}
void dfs2(int x)
{
if(fa[x][0])
rt[x]=rt[fa[x][0]];
for(auto y:vec[x])
rt[x]=update(rt[x],0,1000000000,y);
for(auto to:g[x])
if(to!=fa[x][0])
dfs2(to);
}
int lca(int x,int y)
{
if(dep[x]<dep[y])
swap(x,y);
for(int i=19;i>=0;i--)
if(dep[fa[x][i]]>=dep[y])
x=fa[x][i];
if(x==y)
return x;
for(int i=19;i>=0;i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i], y=fa[y][i];
return fa[x][0];
}
int query(int rt1,int rt2,int rt3,int l,int r,int sum)
{
if(l==r)
{
if(l==0)
return res[rt1].sz+res[rt2].sz-res[rt3].sz*2;
else
return min(res[rt1].sz+res[rt2].sz-res[rt3].sz*2,sum/l);
}
int mid=(l+r)/2, lsum=res[res[rt1].lc].sum+res[res[rt2].lc].sum-res[res[rt3].lc].sum*2;
if(lsum<sum)
return res[res[rt1].lc].sz+res[res[rt2].lc].sz-res[res[rt3].lc].sz*2+query(res[rt1].rc,res[rt2].rc,res[rt3].rc,mid+1,r,sum-lsum);
return query(res[rt1].lc,res[rt2].lc,res[rt3].lc,l,mid,sum);
}
signed main()
{
int n,m,q;
cin >> n >> m >> q;
for(int i=1;i<n;i++)
{
scanf("%lld %lld",&x[i],&y[i]);
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
dep[1]=1;
dfs1(1);
for(int i=1;i<=m;i++)
{
int p,c;
scanf("%lld %lld",&p,&c);
if(fa[x[p]][0]==y[p])
vec[x[p]].push_back(c);
else
vec[y[p]].push_back(c);
}
dfs2(1);
for(int i=1;i<=q;i++)
{
int s,t,x,y;
scanf("%lld %lld %lld %lld",&s,&t,&x,&y);
int LCA=lca(s,t);
int mincost=res[rt[s]].sz+res[rt[t]].sz-res[rt[LCA]].sz*2-query(rt[s],rt[t],rt[LCA],0,1000000000,y);
if(mincost>x)
printf("-1\n");
else
printf("%lld\n",x-mincost);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 16528kb
input:
1831 1865 1153 832 1698 1672 1619 634 920 328 1244 571 1279 1673 1815 1098 92 1320 432 244 636 991 1446 308 569 1118 1356 1733 71 497 1679 1699 635 1254 1295 853 345 364 1396 1183 1134 524 1557 1642 1262 1767 459 918 794 1644 539 902 1046 334 1789 1691 1548 1298 520 1763 216 1161 1065 682 1167 1282 ...
output:
378730605 649537044 339843141 362013697 600127619 123276007 749019778 22 29 54569538 -1 26669081 33 255375699 -1 7 8 -1 427653834 2 8 18 6 9 -1 7 6 265022184 218253041 -1 24 849614439 9 29092527 539604026 0 5 -1 6 -1 12 7 -1 21 -1 13 10 26 6 -1 1 0 546008661 3 6 86261072 -1 448122840 873577464 -1 0 ...
result:
wrong answer 9th numbers differ - expected: '30', found: '29'
Subtask #2:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 179ms
memory: 124348kb
input:
99819 89735 60985 59741 24953 61387 12293 53761 1828 60970 60534 40598 48807 21876 21232 29527 13335 84269 40756 89571 12996 25757 40587 52477 63347 41372 69243 16391 58678 40854 39513 84384 91744 62938 60371 81932 45504 34121 54746 51945 14294 883 85344 78845 51797 45025 76590 37694 65493 4118 2588...
output:
35 -1 12 59 8 5 652673843 2 422622756 -1 -1 -1 29 -1 -1 -1 12 427634455 18 265926271 263974211 877045993 8 288833077 997549690 644774220 16 995218986 30 29 924036742 19 18 1 -1 9 -1 4393606 22 1 932888431 991013529 14 13 -1 6 -1 19 1 19 7 502124020 726366843 1 23 119719836 -1 25 217737158 -1 9415918...
result:
wrong answer 1st numbers differ - expected: '36', found: '35'
Subtask #3:
score: 0
Wrong Answer
Test #59:
score: 0
Wrong Answer
time: 187ms
memory: 105572kb
input:
95629 64841 64314 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51...
output:
-1 701714740 -1 610354140 816755067 2439 245932872 -1 29509 866966613 744072492 889 -1 969398264 588051152 381506396 2346 5426 4829 44376 195466300 60823 507 459304253 400544113 -1 787773518 3855 9692 6576 322820913 900985028 1472 14690 26175 -1 27082 -1 9735 3846 537036842 -1 261459575 86657 635912...
result:
wrong answer 6th numbers differ - expected: '2440', found: '2439'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%