QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#767819 | #7767. 数据结构 | zhouhuanyi | 45 | 2996ms | 424152kb | C++17 | 7.1kb | 2024-11-20 22:15:40 | 2024-11-20 22:15:42 |
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)};
}
struct lines
{
int x,y,data;
bool operator < (const lines &t)const
{
return data<t.data;
}
};
lines dque[N+1];
int n,m,tops,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<int>p[N+1][4];
vector<reads>dp[N+1][4];
vector<reads>DP[N+1][4];
vector<reads>DP2[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>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);
if (sp.size()>=40) sp.clear(),sp.shrink_to_fit();
return sp;
}
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)
{
dfn[x]=++leng,rev[dfn[x]]=x;
if (ES[x].empty()) dque[++tops]=(lines){top[x],x,depth[top[x]]};
if (hs[x]) top[hs[x]]=top[x],dfs2(hs[x]);
for (int i=0;i<ES[x].size();++i)
if (ES[x][i]!=hs[x])
top[ES[x][i]]=ES[x][i],dfs2(ES[x][i]);
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]),DP2[x]=DP2[x]+DP2[ES[x][i]];
}
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;
n=read(),m=read();
for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
depth[1]=1,dfs(1);
for (int i=1;i<=n;++i)
{
x=i;
for (int j=0;j<=3;++j)
{
if (x) p[x][j].push_back(i);
x=fa[x];
}
}
top[1]=1,dfs2(1),sort(dque+1,dque+tops+1);
for (int i=1;i<=tops;++i)
{
x=dque[i].x;
while (x)
{
if (!num[x]) num[x]=++length;
x=hs[x];
}
for (int j=0;j<=2;++j)
{
x=dque[i].x;
while (x)
{
for (int k=0;k<ES[x].size();++k)
if (ES[x][k]!=hs[x])
{
for (int t=0;t<p[ES[x][k]][j].size();++t)
if (!num[p[ES[x][k]][j][t]])
num[p[ES[x][k]][j][t]]=++length;
}
x=hs[x];
}
}
}
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)
{
dp[j][i]=dp[j][i-1];
for (int t=0;t<E[j].size();++t) dp[j][i]=dp[j][i]+dp[E[j][t]][i-1];
}
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;
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 72ms
memory: 188864kb
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:
37227703492 2136305359188 2794367845468 1309925069860 1698169768858 2678958746332 6690595071246 2087826052960 5786332239171 2186592622 4014965079076 1674542130 6524658548 7094033144666 10065416610040 11589693473717 492570862 3356228199498 2834694279 4198036633070 4395772262 4221137767 9630829210 992...
result:
ok 2559 numbers
Test #2:
score: 10
Accepted
time: 48ms
memory: 189440kb
input:
5000 5000 54 2 1945 3 4131 4 1207 5 3558 6 3582 7 1648 8 3498 9 1761 10 360 11 3617 12 4359 13 158 14 2314 15 529 16 4619 17 1070 18 1504 19 2675 20 2981 21 2142 22 1349 23 1640 24 1374 25 4059 26 2511 27 2708 28 2939 29 3017 30 3320 31 4602 32 4779 33 2697 34 3906 35 1121 36 197 37 1551 38 1119 39 ...
output:
0 198262395 0 0 1595057854 0 0 39277179818 13451201574 21469030838 0 0 23554220364 19140694248 212211615641 0 0 0 0 0 86500798 60136122614 47351162248 0 0 306346383502 230306838988 0 170207438 471673864986 387605196674 0 0 0 688392707 115968801311 199501119668 168720065378 634329317954 0 0 155717506...
result:
ok 2456 numbers
Subtask #2:
score: 10
Accepted
Test #3:
score: 10
Accepted
time: 2322ms
memory: 415480kb
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: 10
Accepted
time: 2996ms
memory: 414840kb
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: 5
Accepted
Test #5:
score: 5
Accepted
time: 761ms
memory: 386488kb
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: 792ms
memory: 388864kb
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: 10
Accepted
Test #7:
score: 10
Accepted
time: 1772ms
memory: 417984kb
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: 10
Accepted
time: 969ms
memory: 388884kb
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: 10
Accepted
time: 1865ms
memory: 414524kb
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: 10
Accepted
Dependency #4:
100%
Accepted
Test #10:
score: 10
Accepted
time: 1987ms
memory: 416084kb
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:
ok 100258 numbers
Test #11:
score: 10
Accepted
time: 1934ms
memory: 424152kb
input:
200000 200000 184821 2 53793 3 183415 4 113765 5 178864 6 46342 7 933 8 197825 9 177971 10 143394 11 99313 12 188890 13 25495 14 60986 15 162307 16 135027 17 145920 18 109359 19 5215 20 75134 21 53020 22 160666 23 30142 24 23800 25 38903 26 121838 27 164296 28 86957 29 89705 30 108331 31 147730 32 2...
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 100336 numbers
Subtask #6:
score: 0
Memory Limit Exceeded
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #12:
score: 15
Accepted
time: 1735ms
memory: 417052kb
input:
200000 200000 1 2 1 3 2 4 2 5 5 6 3 7 2 8 3 9 4 10 7 11 9 12 7 13 2 14 12 15 6 16 5 17 14 18 3 19 14 20 13 21 8 22 7 23 12 24 5 25 3 26 18 27 9 28 8 29 6 30 22 31 5 32 6 33 28 34 19 35 24 36 24 37 35 38 7 39 32 40 20 41 19 42 14 43 1 44 5 45 30 46 9 47 30 48 5 49 44 50 7 51 13 52 11 53 19 54 31 55 4...
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 540038770 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100044 numbers
Test #13:
score: 0
Memory Limit Exceeded
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 0 0 0 0 0 510 0 0 0 0 0 0 0 0 405 0 0 0 12322 0 1670 283520 0 0 0 0 0 407680 177845 0 405 0 0 0 0 1464 490 61 0 0 465860 0 16472 0 1534 265620 422870 767 0 0 0 788 280990 322 0 0 198 893 79486 0 767 0 0 0 0 0 0 40 1300 114170 14950 280978 0 0 58950 296946 436080 1512 9726 0 0 226707 325962 312984 ...
result:
Subtask #7:
score: 0
Time Limit Exceeded
Dependency #2:
100%
Accepted
Dependency #4:
100%
Accepted
Test #17:
score: 15
Accepted
time: 2515ms
memory: 417460kb
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
Time Limit Exceeded
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:
1255 2433795 1964764 29610 23717 31723 3955911 23645 26156 24271 0 5061986 44062 10493949 985908 8761 10779313 10728779 9340774 67665 15346404 65472 14456534 63561 61791 68174 1589016 68134 71263 1927247 1819693 83323 85878 1305563 24227309 101761 92443 17871367 25711555 96440 14314220 109965 127220...
result:
Subtask #8:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
0%