QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#178599 | #6332. Two Currencies | RNG_Sword_S11 | 30 | 944ms | 842960kb | C++14 | 3.2kb | 2023-09-14 08:52:45 | 2023-09-14 08:52:46 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed rt[800010];
pair<int,int> operator+(pair<int,int> x,pair<int,int> y)
{
return make_pair(x.first+y.first,x.second+y.second);
}
namespace ds1
{
int t[50000010];
signed cnt[50000010],ls[50000010],rs[50000010],tot=0;
void update(signed &x,int l,int r,int p,int v)
{
if(!x)
x=++tot;
t[x]+=v;cnt[x]++;
if(l==r)
return ;
int mid=(l+r)/2;
if(p<=mid)
update(ls[x],l,mid,p,v);
else
update(rs[x],mid+1,r,p,v);
}
vector<int> cur;
int query(int l,int r,int k)
{
if(l==r)
return (k/l);
int lcnt=0,lsum=0,mid=(l+r)/2;
for(int x:cur)
lcnt+=cnt[ls[x]],lsum+=t[ls[x]];//cout<<x<<' ';
// cout<<endl;
if(lsum<=k)
{
for(int &x:cur)
x=rs[x];
return query(mid+1,r,k-lsum)+lcnt;
}
for(int &x:cur)
x=ls[x];
return query(l,mid,k);
}
};
vector<int> v;
namespace ds2
{
void insert(int x,int l,int r,int p,int v)
{
ds1::update(rt[x],1,1e9,v,v);
if(l==r)
return ;
int mid=(l+r)/2;
if(p<=mid)
insert(x<<1,l,mid,p,v);
else
insert(x<<1|1,mid+1,r,p,v);
}
void findit(int x,int l,int r,int ll,int rr)
{
if(r<ll||rr<l)
return ;
if(ll<=l&&r<=rr)
{
v.push_back(rt[x]);
return ;
}
int mid=(l+r)/2;
findit(x<<1,l,mid,ll,rr);
findit(x<<1|1,mid+1,r,ll,rr);
}
};
vector<int> e[200010],id[200010];
int n,m,q;
vector<int> cc[200010];
vector<int> val[200010];
namespace ds3
{
int fa[200010],sz[200010],dfn[200010],cnt=0;
int top[200010],mxson[200010],dp[200010];
int sum[200010];
void dfs1(int x,int pre)
{
fa[x]=pre;sz[x]=1;dp[x]=dp[pre]+1;
sum[x]=sum[pre]+val[x].size();
for(int y:e[x])
if(y!=pre)
{
dfs1(y,x),sz[x]+=sz[y];
if(sz[y]>sz[mxson[x]])
mxson[x]=y;
}
}
void dfs2(int x,int pre)
{
dfn[x]=++cnt;top[x]=pre;
for(int y:val[x])
ds2::insert(1,1,n,dfn[x],y);
if(mxson[x])
dfs2(mxson[x],pre);
for(int y:e[x])
if(y!=fa[x]&&y!=mxson[x])
dfs2(y,y);
}
int query(int x,int y,int v)
{
::v.clear();
int ans=sum[x]+sum[y];
// cout<<ans<<endl;
while(top[x]!=top[y])
{
if(dp[x]<dp[y])
swap(x,y);
// cout<<dfn[top[x]]<<' '<<dfn[x]<<endl;
ds2::findit(1,1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
if(dp[x]>dp[y])
swap(x,y);
// cout<<dfn[x]+1<<' '<<dfn[y]<<endl;
if(x!=y)
ds2::findit(1,1,n,dfn[x]+1,dfn[y]);
ans-=2*sum[x];
ds1::cur=::v;
// cout<<ans<<endl;
return ans-ds1::query(1,1e9,v);
}
void build()
{
dfs1(1,0);
dfs2(1,1);
}
};
void dfs(int x,int pre)
{
for(int i=0;i<e[x].size();i++)
{
int y=e[x][i];
if(y==pre)
continue;
for(int z:cc[id[x][i]])
val[y].push_back(z);
dfs(y,x);
}
}
signed main()
{
scanf("%lld%lld%lld",&n,&m,&q);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%lld%lld",&x,&y);
e[x].push_back(y);id[x].push_back(i);
e[y].push_back(x);id[y].push_back(i);
}
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%lld%lld",&x,&y);
cc[x].push_back(y);
}
dfs(1,0);ds3::build();
while(q--)
{
int x,y,a,b;
scanf("%lld%lld%lld%lld",&x,&y,&a,&b);
int res=max(ds3::query(x,y,b),0ll);
if(res<=a)
printf("%lld\n",a-res);
else
puts("-1");
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 12ms
memory: 42832kb
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 21 54569538 -1 26669081 33 255375699 0 7 4 -1 427653834 2 9 17 5 4 -1 8 -1 265022184 218253041 -1 24 849614439 4 29092527 539604026 0 -1 -1 6 -1 12 8 -1 22 -1 13 11 26 7 -1 2 0 546008661 2 6 86261072 -1 448122840 873577464 -1 -...
result:
wrong answer 9th numbers differ - expected: '30', found: '21'
Subtask #2:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 317ms
memory: 141096kb
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:
36 -1 6 53 -1 -1 652673843 -1 422622756 -1 -1 -1 29 -1 -1 -1 -1 427634455 18 265926271 263974211 877045993 8 288833077 997549690 644774220 16 995218986 31 24 924036742 5 19 2 -1 4 -1 4393606 22 -1 932888431 991013529 8 10 -1 0 -1 19 -1 14 8 502124020 726366843 -1 24 119719836 -1 19 217737158 -1 9415...
result:
wrong answer 3rd numbers differ - expected: '12', found: '6'
Subtask #3:
score: 30
Accepted
Test #59:
score: 30
Accepted
time: 511ms
memory: 574600kb
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 2440 245932872 -1 29509 866966613 744072492 890 -1 969398264 588051152 381506396 2347 5427 4829 44377 195466300 60823 508 459304253 400544113 -1 787773518 3856 9692 6576 322820913 900985028 1473 14691 26175 -1 27082 -1 9735 3846 537036842 -1 261459575 86658 635912...
result:
ok 64314 numbers
Test #60:
score: 0
Accepted
time: 453ms
memory: 468520kb
input:
92502 51399 68929 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:
36266 -1 -1 112572200 27068354 -1 10394 329233107 444229297 223185833 363055390 1754 14433 -1 4346 -1 33082 457460095 -1 5482 749013593 717085104 5006 -1 926464006 1983 589805099 7590 264497528 8979 903766762 24704 903 923960764 4211 53272133 17012 435443676 -1 984123705 -1 1980 -1 2907 20373 813690...
result:
ok 68929 numbers
Test #61:
score: 0
Accepted
time: 708ms
memory: 729640kb
input:
53810 92751 89379 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:
462043454 6397 31647 98446547 81496 14 34784 1587 532169187 35742 753712897 400460299 299860851 -1 26049 984595650 8185 13794 721579357 166901630 16093 -1 48327 52280 -1 36956 49549 33065 703982006 15511 171757272 130683368 -1 16949 -1 96442497 948433381 -1 -1 -1 3 55603 -1 120939988 12974 952750599...
result:
ok 89379 numbers
Test #62:
score: 0
Accepted
time: 944ms
memory: 842100kb
input:
100000 100000 100000 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...
output:
22357 29573 45104 2184 -1 109258 31337 -1 26387 41578 8392 36172 1160 9470 -1 6923 -1 -1 302 26401 -1 52971 25666 1970 104774 -1 33764 -1 -1 43624 5470 26387 38352 -1 8495 8983 7396 8448 4711 72385 -1 4832 -1 5388 4583 1151 38790 30979 -1 17732 28535 45088 -1 -1 97310 15663 92961 12755 949 -1 22729 ...
result:
ok 100000 numbers
Test #63:
score: 0
Accepted
time: 918ms
memory: 842668kb
input:
100000 100000 100000 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...
output:
6483 8781 -1 24456 222 -1 12374 98 41520 29393 -1 12028 17768 6307 74435 24594 11204 16315 48834 4474 4600 27773 -1 60970 14035 -1 -1 24779 -1 43438 18890 33556 -1 12374 -1 94129 30482 14337 40498 -1 57947 -1 44294 49557 -1 -1 9235 9347 -1 38102 23295 102062 10387 -1 25191 107152 7034 71071 -1 -1 -1...
result:
ok 100000 numbers
Test #64:
score: 0
Accepted
time: 899ms
memory: 842960kb
input:
100000 100000 100000 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...
output:
6354 42704 101441 2857 -1 5542 731 16360 9695 3884 -1 27833 3621 2789 57396 17523 -1 -1 44325 575 7390 -1 -1 39509 17011 27425 -1 12285 62336 -1 -1 -1 -1 3146 273 25050 37917 50109 35442 31916 3096 47751 65204 -1 34032 39181 -1 27586 -1 30894 -1 -1 24707 2796 18515 45391 99909 15335 10383 10905 -1 3...
result:
ok 100000 numbers
Test #65:
score: 0
Accepted
time: 927ms
memory: 728708kb
input:
100000 100000 100000 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...
output:
2311 -1 24585 99022 24662 57394 69711 535 27286 32344 2731 9879 -1 27909 49883 1296 14120 40331 40056 -1 -1 12185 19154 16114 -1 277 23779 -1 -1 13181 52941 31439 10184 -1 3425 5039 -1 80057 -1 253 2188 89575 6499 -1 21752 75653 -1 56204 -1 25131 -1 47353 -1 3783 -1 25426 33521 -1 44916 15271 3317 1...
result:
ok 100000 numbers
Test #66:
score: 0
Accepted
time: 846ms
memory: 717924kb
input:
100000 100000 100000 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...
output:
2587 12143 16964 21386 -1 101210 -1 6285 2557 13670 20738 43749 919 53823 4494 98909 -1 65499 670 -1 21401 2009 66503 -1 -1 49535 62266 37556 6535 731 -1 111804 4842 3527 3557 1260 30321 68998 57960 11241 26780 2411 74629 60899 92019 73225 9479 -1 13551 2534 1509 13677 3454 113005 11 -1 3573 9791 -1...
result:
ok 100000 numbers
Test #67:
score: 0
Accepted
time: 935ms
memory: 728268kb
input:
100000 100000 100000 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...
output:
77660 52 106332 14061 3270 105 18174 -1 77805 50254 969 2318 4576 4994 31416 -1 12558 24255 6163 112456 -1 3285 65589 1757 18715 8429 -1 12879 25335 21564 85094 800 -1 6169 7190 696 7335 5834 11350 58406 -1 49158 39385 45499 -1 22975 -1 18130 103 50778 15483 23138 10195 1015 2379 -1 -1 -1 100907 -1 ...
result:
ok 100000 numbers
Test #68:
score: 0
Accepted
time: 633ms
memory: 841632kb
input:
100000 100000 100000 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...
output:
8988 -1 14443 -1 9877 566 9580 29456 4906 1691 2002 -1 11435 16258 6720 25040 3685 10643 13471 -1 -1 2122 20594 21629 -1 2249 -1 7575 -1 26840 3457 -1 16212 27410 -1 12628 735 35566 9707 33849 -1 -1 14253 7281 -1 29983 22468 17260 -1 26884 32563 5205 32034 18537 -1 23089 -1 -1 20489 16040 -1 14918 3...
result:
ok 100000 numbers
Test #69:
score: 0
Accepted
time: 576ms
memory: 841692kb
input:
100000 100000 100000 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...
output:
1742 787 2082 1836 -1 -1 1627 5815 -1 4401 4394 3625 1587 -1 -1 -1 4148 -1 -1 8136 6572 5217 1943 2258 -1 3108 3768 4306 -1 4910 -1 133 4849 -1 5841 3316 1800 960 1422 -1 -1 1551 2020 6543 5501 1369 969 2603 7944 -1 1593 2764 1249 -1 3673 2691 2441 -1 -1 525 6117 6052 -1 7356 1396 319 1791 3598 5547...
result:
ok 100000 numbers
Test #70:
score: 0
Accepted
time: 685ms
memory: 840480kb
input:
100000 100000 100000 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...
output:
18837 23143 -1 8074 17906 23043 22447 4474 -1 -1 -1 23669 18990 8666 30486 13797 15263 7816 37953 8640 11509 -1 -1 29212 -1 18317 11521 1666 35408 -1 40547 15656 36307 -1 32990 44551 -1 -1 982 22202 -1 25209 -1 14796 687 3218 30059 2421 6558 7656 2579 -1 -1 -1 46022 -1 18254 38968 24549 19782 -1 144...
result:
ok 100000 numbers
Test #71:
score: 0
Accepted
time: 662ms
memory: 842788kb
input:
100000 100000 100000 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...
output:
17013 -1 41429 -1 9558 14122 4177 2863 6179 10012 18668 -1 22362 -1 7604 1525 -1 1695 21676 9201 14992 11539 13085 5285 125129 9680 7725 -1 2697 7054 -1 -1 12370 2872 14385 -1 11028 -1 4915 10533 19472 8246 -1 19183 -1 8850 -1 9950 -1 -1 12145 3988 4652 8232 -1 1884 63752 -1 18594 14048 9432 1651 79...
result:
ok 100000 numbers
Subtask #4:
score: 0
Skipped
Dependency #1:
0%