QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#330914 | #7767. 数据结构 | liuhangxin | 0 | 1142ms | 310696kb | C++14 | 4.4kb | 2024-02-17 20:49:41 | 2024-02-17 20:49:42 |
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,int 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];
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]);
}
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;j++,x=f[x])
for(pii t:kf[x][i-j])
kdis[u][i].push_back(t);
merge(kdis[u][i]);
}
merge(tr[u]);
}
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()
{
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);
dfs3(1,0);
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);
getpath(x,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: 18ms
memory: 98336kb
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:
63813746668 39706791136 41564728985548 42540773244 121482887432 39364631015830 192080633293713 222053365360 160651365198526 58443325738 148624226971416 86429859858 129989122842 229619604627205 103973077436 356223942862388 51496190160 115658467372 82893877703 139223400080 229421255832 95104574163 198...
result:
wrong answer 1st numbers differ - expected: '37227703492', found: '63813746668'
Subtask #2:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 1126ms
memory: 305472kb
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 617528288 617528288 1420484825030 45822091130 349250110352 322280427224 135744407868 1662473271302 1811197159865 110296676908 2213032527764 2667529773780 339104513688 344421089520 2168667686253 301069727060 74741665870800 2713010572002 179479423105627 1737685482768 4496553265184 2259517589856 7410...
result:
wrong answer 2nd numbers differ - expected: '0', found: '617528288'
Subtask #3:
score: 0
Wrong Answer
Test #5:
score: 0
Wrong Answer
time: 569ms
memory: 283536kb
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 987694439181864 294904735015160 20917805624 4212298888 1354054554517552 597518041305560 1430292219687481 2356617911629240 2387977729131424 1264903636419031 2013130649895136 12395717844 6295231442 6295231442 31096948872 82246051928 5053414463990073 5450467434109353 1356343103242207 84323030630 5169...
result:
wrong answer 2nd numbers differ - expected: '134315201201061', found: '987694439181864'
Subtask #4:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 1142ms
memory: 310696kb
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 1247170154 2813454720 0 4220182080 5333510560 5333510560 2276086476 5333510560 14378532276 5942095984 36797844924 25928778672 0 3151398896 21286519544 23157597032 27952107880 26512821492 14335620872 14272373408 31583769068 25393717948 14028666558 54960548168 14007203712 3501800928 80998045536 ...
result:
wrong answer 4th numbers differ - expected: '0', found: '1247170154'
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%