QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#330941 | #7767. 数据结构 | liuhangxin | 10 | 1268ms | 318328kb | C++14 | 4.8kb | 2024-02-17 21:11:17 | 2024-02-17 21:11:17 |
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;
}
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 23ms
memory: 98024kb
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 0 866944956 0 0 433472478 2797400513982 3447996034 3422226834010 1674542130 2580705822430 1674542130 2601977518 4172869665681 1970283448 5876940667610 492570862 2955425172 1300988759 2601977518 985141724 4221137767 5059140822 4433137758 11420259857812 3104154008 1198834818 43831569640 17706992877 ...
result:
wrong answer 1st numbers differ - expected: '37227703492', found: '0'
Subtask #2:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 1203ms
memory: 298480kb
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 3288575788 4176911055 0 4745654848 6222845818 0 0 6585551621 0 1424960716 5224818790 9459319003 5224818790 8673060864 0 11610197664 0 0 9587792729 0 0 0 2747489046 12425650803 0 0 11191496476 0 26203160421 0 0 15164651949 14868775382 4739127362 0 16391028892 0 15726757336 0 176790179...
result:
wrong answer 9th numbers differ - expected: '7615073807', found: '3288575788'
Subtask #3:
score: 0
Wrong Answer
Test #5:
score: 0
Wrong Answer
time: 475ms
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 38336201012364 26918248357976 0 0 38338739596959 38333746483861 77988981576370 95653356124529 96774902656953 97710351122380 151494439192539 0 292392954 292392954 1461964770 13881102848 427543401955315 444106202085724 179351281418256 1876968615 289567928374276 484294649729593 877178862 312780839539...
result:
wrong answer 2nd numbers differ - expected: '134315201201061', found: '38336201012364'
Subtask #4:
score: 10
Accepted
Test #7:
score: 10
Accepted
time: 1235ms
memory: 304044kb
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: 676ms
memory: 250884kb
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: 1268ms
memory: 318328kb
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: 1231ms
memory: 303592kb
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: 0
Skipped
Dependency #2:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
0%