QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#330943 | #7767. 数据结构 | liuhangxin | 35 | 1790ms | 343044kb | C++14 | 4.8kb | 2024-02-17 21:13:31 | 2024-02-17 21:13:31 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
int n,m;
vector<int>to[N];
int f[N],top[N],siz[N],son[N],dep[N];
void dfs(int u,int fa)
{
siz[u]=1;f[u]=fa;dep[u]=dep[fa]+1;
for(int v:to[u])
{
if(v==fa)continue;
dfs(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs4(int u,int f,int t){
top[u]=t;
if(son[u])dfs4(son[u],u,t);
for(int v:to[u]){
if(v==f||v==son[u])continue;
dfs4(v,u,v);
}
}
int tot,dfn[N];
#define VP vector<pii>
void merge(VP &nw)
{
VP ans;
sort(nw.begin(),nw.end());
for(pii t:nw)
if(ans.size()&&ans.back().se+1==t.fi)
ans.back().se=t.se;
else ans.push_back(t);
nw=ans;
}
void bh(int u,int d)
{
if(d==0){
if(!dfn[u])
dfn[u]=++tot;
return;
}
for(int v:to[u])
{
if(v==f[u])continue;
bh(v,d-1);
}
}
void dfsbh(int u,int fa)
{
if(top[u]==u)
{
if(!dfn[u])dfn[u]=++tot;
int nw=u;
while(son[nw]){
nw=son[nw];
if(!dfn[nw])
dfn[nw]=++tot;
}
for(int i=1;i<=3;i++){
int nw2=u;
while(nw2){
for(int v:to[nw2])
if(v!=son[nw2])
bh(v,i-1);
nw2=son[nw2];
}
}
}
if(son[u])dfsbh(son[u],u);
for(int v:to[u])
{
if(v==fa||v==son[u])continue;
dfsbh(v,u);
}
}
struct SEG{
ull a[N],b[N];
inline int lowbit(int x){return x&-x;}
void add(int p,ull v){
ull x=p*v;
for(int i=p;i<N;i+=lowbit(i))a[i]+=v,b[i]+=x;
}
void Add(int l,int r,int v){
add(l,v),add(r+1,-v);
}
ull Pre(int p){
ull res=0;
for(int i=p;i;i-=lowbit(i))res+=a[i]*(p+1)-b[i];
return res;
}
ull qry(int l,int r){return Pre(r)-Pre(l-1);}
}T;
VP tr[N],kdis[N][4],kf[N][4],kans[N][4],kson[N][4];
void Add(VP &nw,VP &x){
for(pii t:x)nw.push_back(t);
}
void dfs2(int u,int fa)//get
{
tr[u].push_back({dfn[u],dfn[u]});
kson[u][0].push_back({dfn[u],dfn[u]});
for(int v:to[u])
if(v!=fa){
dfs2(v,u),Add(tr[u],tr[v]);
for(int j=0;j<=3;j++)
kf[v][j]=kson[u][j];
for(int j=1;j<=3;j++)
Add(kson[u][j],kson[v][j-1]),merge(kson[u][j]);
}
int len=to[u].size();
VP tmp[4];
for(int i=len-1;i>=0;i--)
{
int v=to[u][i];
if(v==fa)continue;
for(int j=1;j<=3;j++)
Add(kf[v][j],tmp[j]),merge(kf[v][j]);
for(int j=1;j<=3;j++)
Add(tmp[j],kson[v][j-1]),merge(tmp[j]);
}
merge(tr[u]);
}
void dfs25(int u,int fa)
{
for(int v:to[u])
if(v!=fa)
dfs25(v,u);
for(int i=0;i<=3;i++)
{
for(int j=0;j<=i;j++)
for(pii t:kson[u][j])
kdis[u][i].push_back(t);
for(int j=1,x=u;j<=i&&x;j++,x=f[x])
for(pii t:kf[x][i-j])
kdis[u][i].push_back(t);
merge(kdis[u][i]);
}
}
void dfs3(int u,int fa)
{
if(u==1)
for(int i=0;i<=3;i++)
kans[u][i]=kdis[u][i];
else
for(int i=0;i<=3;i++){
kans[u][i]=kans[fa][i];
Add(kans[u][i],kson[u][i]);
merge(kans[u][i]);
}
for(int v:to[u]){
if(v==fa)continue;
dfs3(v,u);
}
}
int lca(int a,int b){
while(top[a]!=top[b]){
if(dep[top[a]]<dep[top[b]])swap(a,b);
a=f[top[a]];
}
return dep[a]<dep[b]?a:b;
}
VP getdel(int x,int y,int k){
VP ans,a=kans[x][k],b=kans[y][k];
sort(a.begin(),a.end());
sort(b.begin(),b.end());
int lena=a.size(),lenb=b.size();
for(int i=0,l=0,r=-1;i<lena;i++)
{
while(l<lenb&&b[l].se<a[i].fi)l++;
while(r<lenb-1&&b[r+1].se<=a[i].se)r++;
if(l>r){
ans.push_back(a[i]);
continue;
}
int cl=a[i].fi;
for(int j=l;j<=r;j++)
{
if(b[j].fi!=cl)
ans.push_back({cl,b[j].fi-1});
cl=b[j].se+1;
}
if(cl<=a[i].se)ans.push_back({cl,a[i].se});
}
merge(ans);
return ans;
}
VP getpath(int x,int y,int k)
{
int l=lca(x,y);
VP a=getdel(x,l,k);
VP b=getdel(y,l,k);
VP c=kdis[l][k];
Add(a,b);Add(a,c);
merge(a);
return a;
}
int main()
{
// freopen("d3.in","r",stdin);
// freopen("d.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
to[a].push_back(b);
to[b].push_back(a);
}
dfs(1,0);
dfs4(1,0,1);
dfsbh(1,0);
dfs2(1,0);
dfs25(1,0);
dfs3(1,0);
// for(int i=1;i<=n;i++)
// cout<<dfn[i]<<" ";puts("");
// for(int i=1;i<=n;i++)
// {
// cout<<i<<endl;
// for(pii t:kans[i][1])
// cout<<t.fi<<"!!"<<t.se<<endl;
// }
for(int i=1;i<=m;i++)
{
int op,x,y,v,k;
scanf("%d%d",&op,&x);
if(op==1){
scanf("%d%d%d",&y,&k,&v);
VP tmp=getpath(x,y,k);
for(pii t:tmp)
T.Add(t.fi,t.se,v);
}
else if(op==2){
scanf("%d",&v);
for(pii t:tr[x])
T.Add(t.fi,t.se,v);
}
else if(op==3){
scanf("%d%d",&y,&k);
VP tmp=getpath(x,y,k);
ull res=0;
for(pii t:tmp)
res+=T.qry(t.fi,t.se);
printf("%llu\n",res);
}
else{
ull res=0;
for(pii t:tr[x])
res+=T.qry(t.fi,t.se);
printf("%llu\n",res);
}
}
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 19ms
memory: 95996kb
input:
5000 5000 1 2 2 3 3 4 4 5 5 6 5 7 6 8 7 9 9 10 8 11 11 12 12 13 12 14 14 15 15 16 16 17 16 18 18 19 18 20 20 21 20 22 22 23 23 24 23 25 23 26 26 27 27 28 28 29 27 30 30 31 29 32 32 33 33 34 32 35 35 36 36 37 35 38 36 39 38 40 38 41 41 42 42 43 43 44 42 45 44 46 45 47 47 48 48 49 48 50 49 51 51 52 52...
output:
36282180522 2134414313248 2794367845468 1308900968876 1696278722918 2678958746332 6688161965793 2086292026895 5786332239171 2186592622 4014965079076 1674542130 6524658548 7093370803092 10059064557343 11588105409348 492570862 3348941084329 2834694279 4195122521413 4395772262 4221137767 9630829210 991...
result:
wrong answer 1st numbers differ - expected: '37227703492', found: '36282180522'
Subtask #2:
score: 10
Accepted
Test #3:
score: 10
Accepted
time: 1023ms
memory: 298500kb
input:
200000 200000 1 2 1 3 1 4 3 5 1 6 1 7 7 8 8 9 2 10 1 11 5 12 1 13 7 14 10 15 2 16 7 17 11 18 5 19 5 20 1 21 16 22 1 23 3 24 20 25 14 26 2 27 6 28 15 29 10 30 15 31 5 32 13 33 12 34 31 35 31 36 36 37 36 38 1 39 28 40 5 41 12 42 41 43 20 44 30 45 22 46 11 47 47 48 45 49 14 50 41 51 3 52 30 53 29 54 6 ...
output:
0 0 0 0 0 0 0 0 7615073807 4176911055 0 4745654848 6222845818 0 0 9739142819 0 1424960716 5224818790 9459319003 13717923473 8673060864 0 11610197664 0 0 9587792729 0 0 0 2747489046 12425650803 0 0 11191496476 0 37597503993 0 0 15164651949 14868775382 15559673116 0 16391028892 0 15726757336 0 2421390...
result:
ok 100169 numbers
Test #4:
score: 0
Accepted
time: 1209ms
memory: 336240kb
input:
200000 200000 121679 2 13340 3 45206 4 112138 5 47397 6 88216 7 173469 8 109861 9 58662 10 130056 11 61155 12 4313 13 196310 14 46189 15 32349 16 143798 17 103215 18 159921 19 27365 20 14332 21 49504 22 64451 23 106931 24 59878 25 177587 26 100555 27 86848 28 793 29 79845 30 150813 31 42854 32 11551...
output:
77900221111 0 0 476439705914 0 216029652830 0 0 631267909751 508097390689 0 29277716182 695169620128 0 809294022024 0 0 829507748883 260130797154 0 1005527232590 109198360548 821333235719 0 0 1265757368752 738460021055 296232170804 845184728833 0 434366813420 0 1922343637889 0 0 0 229703081048 0 441...
result:
ok 100073 numbers
Subtask #3:
score: 0
Wrong Answer
Test #5:
score: 0
Wrong Answer
time: 457ms
memory: 258836kb
input:
200000 200000 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 51 ...
output:
0 134315028896099 38210069287857 75888509018259 25202593262786 179527248054069 75824472356207 156951569638953 246509631358547 251383207461179 181645879044485 285463143130322 213796043841569 244908385583039 53375895750478 450587856840 379327308818961 720758846292557 768646001239774 224741684687567 18...
result:
wrong answer 2nd numbers differ - expected: '134315201201061', found: '134315028896099'
Subtask #4:
score: 10
Accepted
Test #7:
score: 10
Accepted
time: 1017ms
memory: 304052kb
input:
200000 200000 1 2 2 3 3 4 1 5 3 6 5 7 5 8 7 9 2 10 7 11 11 12 10 13 6 14 3 15 14 16 4 17 11 18 3 19 14 20 4 21 4 22 12 23 18 24 5 25 5 26 14 27 13 28 24 29 11 30 26 31 29 32 28 33 31 34 23 35 33 36 6 37 11 38 22 39 13 40 35 41 37 42 21 43 12 44 4 45 16 46 12 47 21 48 1 49 26 50 45 51 41 52 46 53 7 5...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 99786 numbers
Test #8:
score: 0
Accepted
time: 605ms
memory: 250888kb
input:
200000 200000 1 2 2 3 1 4 1 5 2 6 3 7 6 8 8 9 8 10 9 11 8 12 12 13 13 14 11 15 13 16 13 17 16 18 17 19 18 20 19 21 19 22 21 23 21 24 21 25 24 26 23 27 26 28 27 29 26 30 30 31 28 32 29 33 32 34 32 35 33 36 36 37 35 38 38 39 38 40 40 41 39 42 42 43 43 44 41 45 45 46 43 47 45 48 46 49 49 50 50 51 51 52...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100404 numbers
Test #9:
score: 0
Accepted
time: 1042ms
memory: 318632kb
input:
200000 200000 166945 2 60190 3 101888 4 154621 5 188595 6 175999 7 140051 8 54071 9 167394 10 54228 11 48270 12 14564 13 25727 14 138072 15 77670 16 77795 17 155644 18 171648 19 94412 20 65323 21 130225 22 6359 23 17410 24 8580 25 142556 26 152863 27 166869 28 115234 29 87099 30 160349 31 98200 32 1...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 99768 numbers
Subtask #5:
score: 0
Wrong Answer
Dependency #4:
100%
Accepted
Test #10:
score: 0
Wrong Answer
time: 1009ms
memory: 303588kb
input:
200000 200000 1 2 1 3 2 4 1 5 2 6 2 7 2 8 5 9 3 10 10 11 5 12 4 13 5 14 9 15 11 16 14 17 12 18 13 19 2 20 16 21 3 22 16 23 2 24 7 25 8 26 20 27 21 28 11 29 12 30 4 31 2 32 21 33 14 34 29 35 16 36 21 37 28 38 22 39 27 40 12 41 36 42 32 43 30 44 3 45 43 46 4 47 14 48 44 49 9 50 37 51 20 52 11 53 31 54...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 348th numbers differ - expected: '1896761708', found: '948380854'
Subtask #6:
score: 0
Skipped
Dependency #4:
100%
Accepted
Dependency #5:
0%
Subtask #7:
score: 15
Accepted
Dependency #2:
100%
Accepted
Dependency #4:
100%
Accepted
Test #17:
score: 15
Accepted
time: 1014ms
memory: 301520kb
input:
200000 200000 1 2 1 3 3 4 1 5 2 6 3 7 1 8 5 9 6 10 9 11 2 12 8 13 3 14 4 15 12 16 10 17 2 18 2 19 14 20 12 21 9 22 19 23 14 24 3 25 13 26 21 27 11 28 5 29 9 30 13 31 13 32 4 33 6 34 14 35 14 36 31 37 13 38 10 39 4 40 28 41 13 42 14 43 20 44 37 45 8 46 14 47 32 48 21 49 40 50 46 51 20 52 44 53 15 54 ...
output:
0 12712803164 0 0 8193968417 14426787309 12950092190 0 32958618613 26764906955 8493139167 0 42785505564 55243799113 0 0 0 0 0 16857343623 27991363871 14151995536 55690427136 85838206842 0 26020925273 22490232861 0 0 1662166464 24948089565 0 26561191640 202942896717 0 91771091757 152033022013 2500525...
result:
ok 100098 numbers
Test #18:
score: 0
Accepted
time: 1790ms
memory: 241084kb
input:
200000 200000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 ...
output:
1506 2433795 1964764 29809 23904 32308 3956297 23683 26194 24496 0 5108618 44498 10494148 1493614 8948 11034059 10983525 9340774 68288 15623342 65908 14673691 63760 62016 68610 3785842 68409 71500 4760847 1843709 83560 86276 3800228 24415019 102280 92867 17894104 25995202 96677 14391781 110124 12872...
result:
ok 99928 numbers
Test #19:
score: 0
Accepted
time: 1116ms
memory: 343044kb
input:
200000 200000 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 ...
output:
0 6432 5572 2146 5686 15024 5924 10437 10836 16481 12732 37909 15933 53994 38493 121364 89269 36850 69524 53517 239542 137860 93122 118688 151902 9279 120973 73158 28901 122575 43850 21781 119189 28818 71155 127221 157054 65948 40570 183418 150579 145757 147361 89223 4664 78041 329787 100673 50134 6...
result:
ok 100068 numbers
Subtask #8:
score: 0
Skipped
Dependency #1:
0%