QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#269442 | #6332. Two Currencies | paul2008# | 0 | 259ms | 124504kb | C++14 | 2.2kb | 2023-11-29 17:09:49 | 2024-07-04 03:11:17 |
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 val)
{
int rt=++cnt;
res[rt]=res[x], res[rt].sz += val, 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,val);
else
res[rt].rc=update(res[x].rc,mid+1,r,y,val);
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],1,1000000000,y,1);
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)
return 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],1,1000000000,y);
if(mincost>x)
printf("-1\n");
else
printf("%lld\n",x-mincost);
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 14628kb
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:
489564527 1036709095 1063710485 392742984 1591534029 615471693 956126648 22 29 643661787 -1 983129482 33 1102117706 -1 7 8 -1 621458139 2 8 18 6 9 -1 7 6 529950077 1129077160 -1 24 1637400385 9 493354078 785690446 0 5 -1 6 -1 12 7 -1 21 -1 13 10 26 6 -1 1 0 1214718881 3 6 130078597 -1 965037699 9817...
result:
wrong answer 1st numbers differ - expected: '378730605', found: '489564527'
Subtask #2:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 209ms
memory: 124504kb
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 1069231327 2 766963197 -1 -1 -1 29 -1 -1 -1 12 444125145 18 292129848 1068454216 1719753505 8 1035486729 1327996658 1406240978 16 1596215544 30 29 1504247625 19 18 1 -1 9 -1 381362911 22 1 1089696991 1434790475 14 13 -1 6 -1 19 1 19 7 960058129 1570009375 1 23 728928962 -1 25 9592048...
result:
wrong answer 1st numbers differ - expected: '36', found: '35'
Subtask #3:
score: 0
Wrong Answer
Test #59:
score: 0
Wrong Answer
time: 259ms
memory: 105808kb
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 1044808866 -1 1560551243 1680858466 2439 1211526409 -1 29509 1002460821 1086724608 889 -1 1080812111 1212591145 1275921602 2346 5426 4829 44376 283904974 60823 507 837102571 947262911 -1 1712492316 3855 9692 6576 798657137 1656135303 1472 14690 26175 -1 27082 -1 9735 3846 1303837223 -1 621963028 ...
result:
wrong answer 2nd numbers differ - expected: '701714740', found: '1044808866'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%