QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#178598 | #6332. Two Currencies | RNG_Sword_S11 | 0 | 590ms | 574488kb | C++14 | 3.2kb | 2023-09-14 08:51:09 | 2023-09-14 08:51:10 |
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=ds3::query(x,y,b);
if(res<=a)
printf("%lld\n",a-res);
else
puts("-1");
}
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 13ms
memory: 44952kb
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 1036709094 1063710485 392742980 1591534029 615471693 956126643 22 21 643661787 -1 983129477 33 1102117706 0 7 4 -1 621458139 2 9 17 5 4 -1 8 -1 529950077 1129077160 -1 24 1637400385 4 493354078 785690446 0 -1 -1 6 -1 12 8 -1 22 -1 13 11 26 7 -1 2 0 1214718881 2 6 130078594 -1 965037695 981...
result:
wrong answer 1st numbers differ - expected: '378730605', found: '489564527'
Subtask #2:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 424ms
memory: 138784kb
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 1069231327 -1 766963193 -1 -1 -1 29 -1 -1 -1 -1 444125143 18 292129848 1068454216 1719753505 8 1035486729 1327996658 1406240978 16 1596215544 31 24 1504247617 5 19 2 -1 4 -1 381362907 22 -1 1089696991 1434790472 8 10 -1 0 -1 19 -1 14 8 960058129 1570009375 -1 24 728928959 -1 19 9592...
result:
wrong answer 3rd numbers differ - expected: '12', found: '6'
Subtask #3:
score: 0
Wrong Answer
Test #59:
score: 0
Wrong Answer
time: 590ms
memory: 574488kb
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 2440 1211526409 -1 29509 1002460821 1086724608 890 -1 1080812111 1212591145 1275921602 2347 5427 4829 44377 283904974 60823 508 837102571 947262911 -1 1712492316 3856 9692 6576 798657137 1656135303 1473 14691 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%