QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#768509 | #7767. 数据结构 | zhouhuanyi | 5 | 621ms | 343064kb | C++14 | 6.3kb | 2024-11-21 11:33:48 | 2024-11-21 11:33:49 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cassert>
#define N 200000
using namespace std;
int read()
{
char c=0;
int sum=0,f=1;
while (c!='-'&&(c<'0'||c>'9')) c=getchar();
if (c=='-') c=getchar(),f=-1;
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum*f;
}
struct reads
{
int l,r;
};
reads operator + (reads a,reads b)
{
return (reads){min(a.l,b.l),max(a.r,b.r)};
}
int n,m,dfn[N+1],leng,depth[N+1],rev[N+1],rev2[N+1],sz[N+1],top[N+1],fa[N+1],hs[N+1],num[N+1],length;
__int128 ans;
bool used[N+1];
vector<int>E[N+1];
vector<int>ES[N+1];
vector<reads>dp[N+1][4];
vector<reads>DP[N+1][4];
vector<reads>DP2[N+1];
vector<reads>DWP[N+1];
bool cmp(int x,int y)
{
return num[x]<num[y];
}
vector<reads>operator + (vector<reads>a,vector<reads>b)
{
if (a.empty()) return b;
if (b.empty()) return a;
int ps=0,ps2=0;
reads d=(reads){0,-1};
vector<reads>sp;
while (ps<a.size()||ps2<b.size())
{
if (ps<a.size()&&(ps2==b.size()||a[ps].l<b[ps2].l))
{
if (d.r+1>=a[ps].l) d=d+a[ps];
else
{
if (d.l<=d.r) sp.push_back(d);
d=a[ps];
}
ps++;
}
else
{
if (d.r+1>=b[ps2].l) d=d+b[ps2];
else
{
if (d.l<=d.r) sp.push_back(d);
d=b[ps2];
}
ps2++;
}
}
sp.push_back(d);
return sp;
}
vector<reads>solve(int l,int r)
{
if (l==r) return DWP[l];
int mid=(l+r)>>1;
return solve(l,mid)+solve(mid+1,r);
}
void add(int x,int y)
{
E[x].push_back(y),E[y].push_back(x);
return;
}
void dfs(int x)
{
used[x]=sz[x]=1;
for (int i=0;i<E[x].size();++i)
if (!used[E[x][i]])
{
fa[E[x][i]]=x,depth[E[x][i]]=depth[x]+1,ES[x].push_back(E[x][i]),dfs(E[x][i]),sz[x]+=sz[E[x][i]];
if (sz[E[x][i]]>sz[hs[x]]) hs[x]=E[x][i];
}
return;
}
void dfs2(int x)
{
int y=x;
vector<int>sp;
vector<int>tp;
while (y) dfn[y]=++leng,sp.push_back(y),top[y]=x,rev[dfn[y]]=y,y=hs[y];
for (int i=0;i<=3;++i)
{
tp.clear();
for (int j=0;j<sp.size();++j)
if (!num[sp[j]])
{
num[sp[j]]=++length;
for (int k=0;k<ES[sp[j]].size();++k) tp.push_back(ES[sp[j]][k]);
}
sp=tp;
}
while (y)
{
for (int i=0;i<ES[y].size();++i)
if (ES[y][i]!=hs[y])
dfs2(ES[y][i]);
y=hs[y];
}
return;
}
void dfs3(int x)
{
for (int i=0;i<ES[x].size();++i)
{
if (ES[x][i]==hs[x])
{
for (int j=0;j<=3;++j) DP[ES[x][i]][j]=DP[ES[x][i]][j]+DP[x][j];
}
dfs3(ES[x][i]);
}
if (!ES[x].empty())
{
for (int i=0;i<ES[x].size();++i) DWP[i+1]=DP2[ES[x][i]];
DP2[x]=DP2[x]+solve(1,ES[x].size());
}
return;
}
struct seg
{
struct node
{
int l,r;
vector<reads>data;
};
node tree[(N<<2)+1];
void push_up(int k)
{
tree[k].data=tree[k<<1].data+tree[k<<1|1].data;
return;
}
void build(int k,int l,int r,int d)
{
tree[k].l=l,tree[k].r=r;
if (l==r)
{
tree[k].data=dp[rev[l]][d];
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid,d),build(k<<1|1,mid+1,r,d),push_up(k);
return;
}
vector<reads>query(int k,int l,int r)
{
if (tree[k].l==l&&tree[k].r==r) return tree[k].data;
int mid=(tree[k].l+tree[k].r)>>1;
if (r<=mid) return query(k<<1,l,r);
else if (l>=mid+1) return query(k<<1|1,l,r);
else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
}
};
seg T[4];
struct seg2
{
struct node
{
int l,r;
long long lazy;
__int128 data;
};
node tree[(N<<2)+1];
void push_up(int k)
{
tree[k].data=tree[k<<1].data+tree[k<<1|1].data;
return;
}
void push_tag(int k,long long d)
{
tree[k].lazy+=d,tree[k].data+=(__int128)(d)*(tree[k].r-tree[k].l+1);
return;
}
void spread(int k)
{
if (tree[k].lazy!=0) push_tag(k<<1,tree[k].lazy),push_tag(k<<1|1,tree[k].lazy),tree[k].lazy=0;
return;
}
void build(int k,int l,int r)
{
tree[k].l=l,tree[k].r=r;
if (l==r) return;
int mid=(l+r)>>1;
build(k<<1,l,mid),build(k<<1|1,mid+1,r),push_up(k);
return;
}
void add(int k,int l,int r,int d)
{
if (tree[k].l==l&&tree[k].r==r)
{
push_tag(k,d);
return;
}
spread(k);
int mid=(tree[k].l+tree[k].r)>>1;
if (r<=mid) add(k<<1,l,r,d);
else if (l>=mid+1) add(k<<1|1,l,r,d);
else add(k<<1,l,mid,d),add(k<<1|1,mid+1,r,d);
push_up(k);
return;
}
__int128 query(int k,int l,int r)
{
if (tree[k].l==l&&tree[k].r==r) return tree[k].data;
spread(k);
int mid=(tree[k].l+tree[k].r)>>1;
if (r<=mid) return query(k<<1,l,r);
else if (l>=mid+1) return query(k<<1|1,l,r);
else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
}
};
seg2 T2;
vector<reads>get_path(int x,int y,int k)
{
vector<reads>sp;
while (top[x]!=top[y])
{
if (depth[top[x]]<depth[top[y]]) swap(x,y);
sp=sp+DP[x][k],x=fa[top[x]];
}
if (depth[x]>depth[y]) swap(x,y);
sp=sp+T[k].query(1,dfn[x],dfn[y]);
return sp;
}
void write(__int128 d)
{
if (!d) return;
write(d/10),printf("%d",(int)(d%10));
return;
}
void output(__int128 d)
{
if (d>0) write(d),puts("");
else if (d==0) puts("0");
else printf("-"),write(-d),puts("");
return;
}
int main()
{
int opt,x,y,d,k;
vector<reads>sp;
vector<int>zp;
n=read(),m=read();
for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
depth[1]=1,dfs(1),dfs2(1);
for (int i=1;i<=n;++i) dp[i][0]={(reads){num[i],num[i]}},rev2[num[i]]=i;
for (int i=1;i<=3;++i)
for (int j=1;j<=n;++j)
{
for (int t=0;t<E[j].size();++t) DWP[t+1]=dp[E[j][t]][i-1];
if (E[j].empty()) dp[j][i]=dp[j][i-1];
else dp[j][i]=dp[j][i-1]+solve(1,E[j].size());
}
for (int i=1;i<=n;++i)
{
for (int j=0;j<=3;++j) DP[i][j]=dp[i][j];
DP2[i]=dp[i][0];
}
dfs3(1);
for (int i=0;i<=3;++i) T[i].build(1,1,n,i);
T2.build(1,1,n);
for (int qt=1;qt<=m;++qt)
{
opt=read();
if (opt==1)
{
x=read(),y=read(),k=read(),d=read(),sp=get_path(x,y,k);
for (int i=0;i<sp.size();++i) T2.add(1,sp[i].l,sp[i].r,d);
}
else if (opt==2)
{
x=read(),d=read(),sp=DP2[x];
for (int i=0;i<sp.size();++i) T2.add(1,sp[i].l,sp[i].r,d);
}
else if (opt==3)
{
x=read(),y=read(),k=read(),sp=get_path(x,y,k),ans=0;
for (int i=0;i<sp.size();++i) ans+=T2.query(1,sp[i].l,sp[i].r);
printf("%llu\n",(unsigned long long)(ans));
}
else
{
x=read(),sp=DP2[x],ans=0;
for (int i=0;i<sp.size();++i) ans+=T2.query(1,sp[i].l,sp[i].r);
printf("%llu\n",(unsigned long long)(ans));
}
}
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: 35ms
memory: 164736kb
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:
0 768923601388 2099590041248 286987402788 752537985644 1930863827318 6227278751095 1747983630208 4234288025924 2186592622 3107678154407 6540025950 7825890790 5062590518238 9178422112172 8484694082565 3710804959 2868904962877 2240142271 6017833058483 4771281709 4221137767 6937447846 0 16124680084935 ...
result:
wrong answer 1st numbers differ - expected: '37227703492', found: '0'
Subtask #2:
score: 0
Runtime Error
Test #3:
score: 0
Runtime Error
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 2248144434 3054888636 3054888636 3054888636 3054888636 0 0 3512495396 0 0 4827589601 4827589601 0 5612893094 0 0 0 0 0 7003161388 0 9357900481 9357900481 0 9467066357 9467066357 9467066357 0 0 9467066357 9467066357 0 9734067900 0 9734067900 9734067900 0 0 0 10616330938 0 10616330938 0 10616330...
result:
Subtask #3:
score: 5
Accepted
Test #5:
score: 5
Accepted
time: 589ms
memory: 343064kb
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 134315201201061 38210069287857 75889674481730 25202765567748 179527420359031 75824479907233 156951577189979 246509811214535 251383387317167 181645886595511 285463150681348 213797241401335 244909583142805 53376921005282 451665818220 379334117147250 720759810155057 768646965102274 224741692238593 18...
result:
ok 100065 numbers
Test #6:
score: 5
Accepted
time: 621ms
memory: 343036kb
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 1950387013442 2906443199266 2144858813468 3137341049831 1081425884175 20924388962208 73530126133368 136609133052209 125022026678010 22502893517249 99022896674514 84010333777754 13909990392191 43442491331837 190816082733002 92810414504491 244006706308139 42843404030538 126151201042579 7249812065288...
result:
ok 99740 numbers
Subtask #4:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 401ms
memory: 248256kb
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:
wrong answer 259th numbers differ - expected: '782172417', found: '0'
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #2:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
0%