QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#748454 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | lizhous | 27 | 262ms | 110944kb | C++14 | 7.2kb | 2024-11-14 20:27:18 | 2024-11-14 20:27:19 |
Judging History
answer
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
#include<set>
#include<queue>
#define mod 998244353
#define int long long
using namespace std;
vector <int> g[200001];
int n,q;
namespace lca
{
int father[200001][21],deep[200001];
void getfather(int u,int fa)
{
father[u][0]=fa;
for(int i=1;i<=20;i++)
{
father[u][i]=father[father[u][i-1]][i-1];
}
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==fa) continue;
getfather(v,u);
}
}
void getdeep(int u,int fa)
{
deep[u]=deep[fa]+1;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==fa) continue;
getdeep(v,u);
}
}
int getlca(int u,int v)
{
if(deep[u]>deep[v]) swap(u,v);
int mul=deep[v]-deep[u],w=0;
while(mul)
{
if(mul&1) v=father[v][w];
mul>>=1;
w++;
}
if(u==v) return u;
for(int i=20;i>=0;i--)
{
if(father[u][i]!=father[v][i])
{
u=father[u][i];
v=father[v][i];
}
}
return father[u][0];
}
}
int ans[200001];
struct qry
{
int d,id,xs;
};
namespace dfz
{
vector <qry> Q[200001];
int anss,mid,masiz[200001],ton[200001],szz;
bool vis[200001];
void add(int x,int v)
{
x++;
while(x<=szz+1)
{
// cout<<x<<"+\n";
ton[x]+=v;
x+=(x&(-x));
}
}
int get(int x,int ret=0)
{
x++;
x=min(x,szz+1);
while(x)
{
// cout<<x<<"G\n";
ret+=ton[x];
x-=(x&(-x));
}
return ret;
}
void getmid(int u,int fa,int sz)
{
int ma=0;
for(int i=0;i<g[u].size();i++)
{
if(g[u][i]==fa||vis[g[u][i]]) continue;
getmid(g[u][i],u,sz);
masiz[u]+=masiz[g[u][i]]+1;
ma=max(ma,masiz[g[u][i]]);
}
ma=max(ma+1,sz-masiz[u]-1);
if(ma<anss)
{
anss=ma;
mid=u;
}
}
int getsiz(int u,int fa)
{
int ret=1;
masiz[u]=0;
for(int i=0;i<g[u].size();i++)
{
if(g[u][i]==fa||vis[g[u][i]]) continue;
ret+=getsiz(g[u][i],u);
}
return ret;
}
void dfs(int u,int fa,int dis,int vsl)
{
add(dis,vsl);
for(int v:g[u])
{
if(v==fa||vis[v]) continue;
dfs(v,u,dis+1,vsl);
}
}
void go(int u,int fa,int dis)
{
for(qry now:Q[u])
{
if(now.d>=dis)
{
////cerr<<now.id<<' '<<get(now.d-dis)<<'\n';
ans[now.id]+=get(now.d-dis);
}
}
for(int v:g[u])
{
if(v==fa||vis[v]) continue;
go(v,u,dis+1);
}
}
void work(int u)
{
//cerr<<">>"<<u<<" : \n";
dfs(u,-1,0,1);
for(int v:g[u])
{
if(vis[v]) continue;
dfs(v,u,1,-1);
go(v,u,1);
dfs(v,u,1,1);
}
for(qry now:Q[u])
{
//cerr<<now.id<<' '<<get(now.d)<<' '<<szz<<'\n';
ans[now.id]+=get(now.d);
}
}
void dfz(int u)
{
// cout<<u<<" midis ";
anss=10000000000;
mid=0;
szz=getsiz(u,-1);
getmid(u,-1,szz);
u=mid;
// cout<<u<<'\n';
// if(g[u].size()==1)
// {
// for(qry now:Q[u])
// {
// ans[now.id]++;
// }
// return;
// }
work(u);
for(int i=0;i<=szz+1;i++) ton[i]=0;
vis[u]=true;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(vis[v]) continue;
dfz(v);
}
}
}
namespace sp
{
int fat[200001],siz[200001],dep[200001],hson[200001],top[200001],cnt,dfn[200001],dis[200001];
int rt[200001],LEN;
struct T
{
int l,r,sum;
}tr[2000001];
void add(int &o,int l,int r,int x,int v)
{
if(!o) o=++LEN;
if(l==r)
{
tr[o].sum+=v;
return;
}
int mid=l+r>>1;
if(x<=mid) add(tr[o].l,l,mid,x,v);
else add(tr[o].r,mid+1,r,x,v);
tr[o].sum=tr[tr[o].l].sum+tr[tr[o].r].sum;
// cout<<o<<" "<<l<<' '<<r<<" : "<<tr[o].sum<<'\n';
}
int get(int o,int l,int r,int x,int y)
{
if(y<l||x>r||!o) return 0;
if(x<=l&&r<=y)
{
return tr[o].sum;
}
int mid=l+r>>1;
return get(tr[o].l,l,mid,x,y)+get(tr[o].r,mid+1,r,x,y);
}
void merg(int &o,int &p)
{
if(!p) return;
if(!o)
{
o=p;
return;
}
merg(tr[o].l,tr[p].l);
merg(tr[o].r,tr[p].r);
tr[o].sum+=tr[p].sum;
}
void getdfsh(int u,int fa)
{
fat[u]=fa;
dep[u]=dep[fa]+1;
int lll=0;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==fa) continue;
getdfsh(v,u);
if(siz[v]>lll)
{
hson[u]=v;
lll=siz[v];
}
siz[u]+=siz[v];
}
siz[u]++;
}
void gettd(int u,int fa)
{
dfn[u] = ++cnt;
dis[u] = cnt;
if(hson[fat[u]]==u)
{
top[u]=top[fa];
}
else
{
top[u]=u;
}
//cerr<<u<<" : "<<top[u]<<'\n';
if(hson[u]!=0) gettd(hson[u],u);
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==fa||v==hson[u]) continue;
gettd(v,u);
}
}
vector <qry> Qg[200001],Qh[200001];
void up(int u,int d,int id,int xs)
{
ans[id]+=dep[u]*xs;
Qg[u].push_back((qry){d,id,xs});
// //cerr<<u<<" : hson "<<hson[u]<<'\n';
Qh[hson[u]].push_back((qry){d-1,id,xs});
int now=top[u];
while(now!=1)
{
// //cerr<<now<<"\n";
Qh[now].push_back((qry){d-1,id,-xs});
Qh[hson[fat[now]]].push_back((qry){d-1,id,xs});
now=top[fat[now]];
}
}
int ton[200001];
void add(int x,int v)
{
// //cerr<<"ADD "<<x<<'\n';
while(x<=n)
{
ton[x]+=v;
x+=(x&(-x));
}
}
int get(int x,int ret=0)
{
// //cerr<<"GET "<<x<<'\n';
while(x)
{
ret+=ton[x];
x-=(x&(-x));
}
return ret;
}
void inton(int u,int fa,int dis,int vsl)
{
add(dis,vsl);
for(int v:g[u])
{
if(v==fa) continue;
inton(v,u,dis+1,vsl);
}
}
void workg(int u,int fa)
{
for(int v:g[u])
{
if(v==fa) continue;
if(v!=hson[u])
{
inton(v,u,1,1);
}
}
for(qry now:Qg[u])
{
ans[now.id]+=now.xs*get(now.d);
}
for(int v:g[u])
{
if(v==fa) continue;
workg(v,u);
}
for(int v:g[u])
{
if(v==fa) continue;
if(v!=hson[u])
{
inton(v,u,1,-1);
}
}
}
void workh(int u,int fa)
{
for(int v:g[u])
{
if(v==fa) continue;
workh(v,u);
merg(rt[u],rt[v]);
}
add(rt[u],1,n,dep[u],1);
for(qry now:Qh[u])
{
if(now.d<0) continue;
//cerr<<u<<" "<<now.d<<" : "<<get(rt[u],1,n,dep[u],dep[u]+now.d)<<" to "<<now.id<<" times "<<now.xs<<'\n';
ans[now.id]+=now.xs*get(rt[u],1,n,dep[u],dep[u]+now.d);
}
}
}
signed main()
{
// freopen("tiv.in","r",stdin);
// freopen("tiv.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1,u,v;i<n;i++)
{
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
lca::getfather(1,0);
lca::getdeep(1,0);
sp::getdfsh(1,0);
sp::gettd(1,0);
cin>>q;
for(int i=1,u,v,d;i<=q;i++)
{
cin>>u>>v>>d;
//cerr<<u<<' '<<v<<' '<<d<<"\n";
int lca=lca::getlca(u,v);
// //cerr<<lca<<" ";
dfz::Q[lca].push_back((qry){d,i,1});
sp::up(u,d,i,1);
sp::up(v,d,i,1);
sp::up(lca,d,i,-2);
}
//cerr<<"SSSS\n";
for(int i=1;i<=q;i++)
{
//cerr<<ans[i]<<'\n';
}
dfz::dfz(1);
//cerr<<"DFZ\n";
for(int i=1;i<=q;i++)
{
//cerr<<ans[i]<<'\n';
}
sp::workg(1,0);
//cerr<<"WORKG\n";
for(int i=1;i<=q;i++)
{
//cerr<<ans[i]<<'\n';
}
sp::workh(1,0);
//cerr<<"WORKH\n";
for(int i=1;i<=q;i++)
{
cout<<ans[i]<<'\n';
}
}
詳細信息
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 11ms
memory: 42016kb
input:
4988 1 2 1 3 1 4 4 5 1 6 3 7 3 8 5 9 4 10 6 11 3 12 9 13 11 14 8 15 11 16 1 17 7 18 8 19 18 20 7 21 10 22 15 23 18 24 4 25 24 26 9 27 23 28 3 29 3 30 30 31 11 32 18 33 2 34 32 35 29 36 29 37 19 38 9 39 6 40 25 41 16 42 31 43 6 44 42 45 32 46 27 47 32 48 44 49 7 50 10 51 24 52 46 53 30 54 46 55 39 56...
output:
3226 2028 4988 208 252 3970 3886 2013 4974 2118 308 391 4768 312 4954 4988 4974 1551 4981 12 1856 4825 4974 4974 19 82 4960 4680 208 4870 474 3693 808 1880 213 3394 1203 266 84 4822 3334 70 81 4501 4960 668 4866 4974 113 490 75 163 209 2159 4981 4143 100 3168 232 66 4864 525 4958 390 4713 2305 15 49...
result:
ok 4966 numbers
Test #2:
score: 7
Accepted
time: 17ms
memory: 47140kb
input:
4914 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 27 54 27 ...
output:
3378 4914 231 4914 4914 3378 22 4914 4914 2559 4914 75 219 1407 1138 863 24 3890 4914 4914 399 399 13 139 77 4914 4095 3071 4914 23 151 110 1407 43 54 4914 4914 1919 2559 77 735 3071 24 133 479 4914 33 831 4 4914 4914 79 4914 199 3890 3071 73 567 15 75 21 126 4914 4914 203 4914 75 127 62 41 4914 409...
result:
ok 4975 numbers
Test #3:
score: 7
Accepted
time: 15ms
memory: 42132kb
input:
4921 1151 2767 2767 322 322 4451 4451 4867 4867 1265 1265 3197 3197 3890 3890 1052 1052 1407 1407 1578 1578 566 566 2965 2965 260 260 4908 4908 308 308 553 553 2845 2845 4249 4249 1284 1284 73 73 1088 1088 277 277 1878 1878 4128 4128 3609 3609 2126 2126 149 149 3467 3467 1653 1653 4913 4913 3604 360...
output:
4921 3192 3260 3983 949 2080 605 3471 4901 2020 2552 1570 3325 3643 458 1296 3072 3423 3045 2569 1720 3195 1908 4397 1536 2799 3072 2443 3176 3311 1403 1119 842 3028 2387 1903 2303 4921 2149 1974 4153 2053 2888 2344 3264 3709 3443 3601 2571 1207 4519 3745 959 1920 1305 1706 1743 522 1266 2153 1812 1...
result:
ok 4930 numbers
Test #4:
score: 7
Accepted
time: 17ms
memory: 39140kb
input:
4942 877 4180 4180 4409 4409 2233 2233 3491 3491 3459 3459 4501 4501 2192 2192 3539 3539 4379 4379 4346 4346 1553 1553 2100 2100 3426 3426 3461 3461 811 811 2981 2981 1493 1493 610 610 599 599 1741 1741 3216 3216 1646 1646 1016 1016 3757 3757 2570 2570 2900 2900 4649 4649 1014 1014 538 538 4288 4288...
output:
4236 3338 4942 4942 4942 4942 1551 1272 3885 4140 4942 3627 3132 3991 3157 4024 4942 4942 3761 3064 238 4942 4942 4942 4942 4942 2256 4942 649 4496 4942 4942 4491 866 4208 4942 4942 4726 4942 4462 4942 4942 4234 2676 2593 4942 4088 4942 2704 3344 3560 4942 4942 4461 4511 4634 3437 2884 3842 4942 494...
result:
ok 4910 numbers
Test #5:
score: 7
Accepted
time: 8ms
memory: 37408kb
input:
4996 1 2 2 3 1 4 4 5 4 6 3 7 4 8 8 9 3 10 9 11 5 12 7 13 12 14 8 15 8 16 14 17 10 18 15 19 17 20 15 21 19 22 21 23 14 24 20 25 25 26 21 27 20 28 19 29 29 30 24 31 31 32 29 33 27 34 34 35 31 36 27 37 30 38 35 39 38 40 37 41 34 42 41 43 43 44 42 45 36 46 37 47 47 48 47 49 41 50 50 51 46 52 50 53 51 54...
output:
4869 3419 3000 4640 4996 4996 3854 4165 4542 4996 1758 3584 3011 4996 4996 4383 2064 4199 2786 2470 4759 4996 4657 4157 2443 2594 1823 3215 1635 3908 1903 3207 2153 4448 4996 4996 3071 2649 3452 4996 1235 1599 2732 2244 2311 4618 1250 4577 3498 4941 1058 3498 3539 3415 907 4170 4996 4144 2235 2664 4...
result:
ok 4952 numbers
Test #6:
score: 7
Accepted
time: 6ms
memory: 42100kb
input:
4935 1 2 1 3 4 2 5 2 6 4 7 4 8 6 9 6 10 8 11 8 12 10 13 10 14 12 15 12 16 14 17 14 18 16 19 16 20 18 21 18 22 20 23 20 24 22 25 22 26 24 27 24 28 26 29 26 30 28 31 28 32 30 33 30 34 32 35 32 36 34 37 34 38 36 39 36 40 38 41 38 42 40 43 40 44 42 45 42 46 44 47 44 48 46 49 46 50 48 51 48 52 50 53 50 5...
output:
4442 4133 346 3268 4850 3512 3312 3581 4092 4655 2256 3950 3157 3480 4935 4188 4935 1593 1135 4935 4935 4875 4108 3771 4158 4935 4935 3156 3148 1814 4935 3368 4303 2861 4917 2370 3992 4764 2772 4935 4935 2640 4935 4691 2291 4268 1798 4530 3058 3219 4935 3141 4935 2699 4547 2164 2495 3049 370 3409 21...
result:
ok 4992 numbers
Test #7:
score: 7
Accepted
time: 13ms
memory: 36912kb
input:
4919 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 52 52 53 ...
output:
2653 3219 4302 1418 1713 713 3341 647 487 1508 971 4851 4443 3078 2380 2267 4171 18 2056 1833 3136 817 4375 4103 3423 433 3967 725 282 2358 4171 1680 3350 2403 802 1855 137 2091 3731 1061 581 1273 4783 133 1911 4239 4233 678 3127 3481 284 1896 435 593 4781 103 4647 1615 1231 2689 574 1833 4783 645 4...
result:
ok 4980 numbers
Test #8:
score: 7
Accepted
time: 24ms
memory: 41860kb
input:
4973 1 4517 2 744 3 1115 4 3191 5 4186 6 4608 7 3898 8 3939 9 1998 10 2287 11 2277 12 4200 13 4935 14 3955 15 3683 16 278 17 547 18 3351 19 2642 20 4050 21 3457 22 2337 23 3435 24 1476 25 4853 26 3985 27 736 28 3016 29 4840 30 3866 31 4567 32 4067 33 3724 34 1872 35 1533 36 4787 37 53 38 1632 39 295...
output:
91 2487 2646 1791 2447 3327 532 1801 1079 1526 1236 77 4028 3401 4103 1573 3540 1641 452 52 2497 3128 2593 734 1293 3213 1786 1626 2130 2033 1935 2673 1758 1838 1284 758 2952 301 947 2875 3073 1462 2615 2842 3561 1969 1416 3088 2476 1082 696 3665 2041 3263 3063 2988 1402 1050 2967 3696 2309 3767 281...
result:
ok 4982 numbers
Subtask #2:
score: 0
Memory Limit Exceeded
Test #9:
score: 0
Memory Limit Exceeded
input:
199995 1 2 2 3 2 4 1 5 3 6 5 7 6 8 4 9 2 10 5 11 5 12 1 13 1 14 1 15 13 16 1 17 10 18 16 19 11 20 8 21 17 22 4 23 19 24 7 25 22 26 8 27 14 28 1 29 9 30 3 31 3 32 21 33 19 34 26 35 34 36 5 37 29 38 22 39 5 40 13 41 28 42 8 43 35 44 22 45 14 46 12 47 32 48 11 49 8 50 18 51 23 52 18 53 4 54 6 55 10 56 ...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Memory Limit Exceeded
Test #25:
score: 0
Memory Limit Exceeded
input:
199991 1 2 2 3 3 4 3 5 5 6 3 7 1 8 8 9 8 10 10 11 1 12 1 13 13 14 4 15 12 16 13 17 17 18 8 19 3 20 9 21 16 22 10 23 1 24 7 25 6 26 12 27 4 28 21 29 27 30 30 31 21 32 19 33 20 34 17 35 7 36 13 37 24 38 37 39 30 40 31 41 15 42 9 43 32 44 41 45 18 46 38 47 8 48 35 49 13 50 35 51 47 52 35 53 48 54 44 55...
output:
result:
Subtask #5:
score: 20
Accepted
Dependency #1:
100%
Accepted
Test #33:
score: 20
Accepted
time: 209ms
memory: 91968kb
input:
49994 1 2 1 3 1 4 4 5 4 6 2 7 5 8 2 9 5 10 3 11 11 12 5 13 2 14 5 15 14 16 15 17 15 18 11 19 7 20 2 21 1 22 21 23 15 24 22 25 16 26 22 27 16 28 11 29 17 30 21 31 3 32 22 33 3 34 33 35 34 36 17 37 22 38 21 39 22 40 11 41 14 42 30 43 42 44 27 45 41 46 21 47 5 48 17 49 40 50 31 51 23 52 40 53 17 54 39 ...
output:
49991 27842 12698 41582 41674 49129 139 49931 49986 49966 33701 41907 520 7 49823 37296 45378 43279 22 45415 43709 139 1658 12239 1106 48337 42014 49964 1603 49935 1295 38134 484 49771 13800 36652 12183 1503 49825 148 49211 195 46766 38915 49990 26440 26888 1176 140 37080 8196 5750 49964 49612 49935...
result:
ok 49997 numbers
Test #34:
score: 20
Accepted
time: 228ms
memory: 110944kb
input:
49994 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 27 54 27...
output:
13823 49994 49994 24 367 48 19455 367 2175 6655 1215 3839 17407 9727 49994 28671 49994 3039 49994 49151 1071 3839 3839 49994 1215 49994 671 3839 49994 591 3711 49994 15359 49994 28 2175 367 28671 10751 49994 11263 98 107 41802 4543 199 36863 49994 49994 1183 367 49151 40959 1071 2111 6655 11263 1927...
result:
ok 49997 numbers
Test #35:
score: 20
Accepted
time: 201ms
memory: 75680kb
input:
49992 18276 49801 49801 29872 29872 18038 18038 5160 5160 47615 47615 9368 9368 48020 48020 18919 18919 22293 22293 28784 28784 26366 26366 16335 16335 996 996 28965 28965 7132 7132 9570 9570 22976 22976 16634 16634 22619 22619 28051 28051 11004 11004 1360 1360 41340 41340 43214 43214 24436 24436 46...
output:
46017 14490 35283 47122 47076 47522 33249 14538 36480 29309 30496 22079 35856 47676 19688 29847 49992 46968 30446 36597 41074 24827 42181 37491 49992 33422 23462 34849 43986 32605 22539 43614 40945 48216 9983 37908 40591 47737 22962 33035 23333 35206 19572 33241 18254 44132 21667 21688 43981 44138 3...
result:
ok 49996 numbers
Test #36:
score: 20
Accepted
time: 190ms
memory: 66300kb
input:
49991 36788 8430 8430 29122 29122 7462 7462 34863 34863 38520 38520 38159 38159 10299 10299 26846 26846 40569 40569 35453 35453 39237 39237 37963 37963 2323 2323 5574 5574 49072 49072 8151 8151 9543 9543 14269 14269 15375 15375 38098 38098 46141 46141 29199 29199 13837 13837 3056 3056 13396 13396 20...
output:
10717 26965 17476 49991 49991 12680 32753 49991 44617 49991 49991 49991 49991 29760 49991 49991 49991 49991 49991 49991 15545 49991 19088 21948 23809 49991 46952 49991 49991 49991 36059 37144 49991 49991 41837 49991 49991 49991 49991 49991 49991 49991 49991 49991 49991 49991 28977 43912 49991 49991 ...
result:
ok 49999 numbers
Test #37:
score: 20
Accepted
time: 183ms
memory: 78124kb
input:
49992 1 2 1 3 3 4 4 5 5 6 6 7 6 8 3 9 9 10 4 11 7 12 6 13 7 14 9 15 10 16 8 17 13 18 18 19 15 20 17 21 19 22 13 23 23 24 21 25 19 26 19 27 23 28 19 29 25 30 27 31 28 32 25 33 30 34 34 35 28 36 32 37 35 38 36 39 34 40 39 41 41 42 39 43 34 44 41 45 36 46 44 47 39 48 48 49 44 50 43 51 44 52 49 53 53 54...
output:
49992 44208 40560 49983 44985 19872 12959 21712 45703 31309 33201 49992 21924 36480 16502 31883 16181 36221 24725 42191 49992 35236 49992 35558 23642 20260 20165 11056 7575 49992 47236 49992 49992 43883 49992 35916 44169 49992 32253 41307 11731 4410 36173 36842 41712 18415 15542 34255 14712 35964 31...
result:
ok 49997 numbers
Test #38:
score: 20
Accepted
time: 154ms
memory: 78864kb
input:
49992 1 2 1 3 4 2 5 2 6 4 7 4 8 6 9 6 10 8 11 8 12 10 13 10 14 12 15 12 16 14 17 14 18 16 19 16 20 18 21 18 22 20 23 20 24 22 25 22 26 24 27 24 28 26 29 26 30 28 31 28 32 30 33 30 34 32 35 32 36 34 37 34 38 36 39 36 40 38 41 38 42 40 43 40 44 42 45 42 46 44 47 44 48 46 49 46 50 48 51 48 52 50 53 50 ...
output:
39583 37249 43384 29100 15677 17788 5806 32912 32417 42927 35958 35935 20363 17412 28393 13083 49992 17231 44476 34557 26645 31001 33105 49992 42169 38467 49992 34467 22711 30648 32377 40585 16552 48257 37613 16909 35471 49992 25468 18922 26730 24191 41997 49299 41755 17953 37963 49992 2358 9448 499...
result:
ok 49991 numbers
Test #39:
score: 20
Accepted
time: 135ms
memory: 70348kb
input:
49992 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 52 52 53...
output:
2119 8453 47550 40224 8275 48438 21511 29343 11178 12840 37338 17769 49992 40224 26178 11775 11405 48882 23283 9518 26016 49548 36450 8684 22461 35730 41556 10352 38656 26589 8503 36628 20425 46879 43554 47994 15804 12373 28369 21219 43776 38004 38886 35562 20679 5674 16613 25704 29120 2178 21055 31...
result:
ok 49990 numbers
Test #40:
score: 20
Accepted
time: 262ms
memory: 85764kb
input:
49996 1 34528 2 1933 3 8542 4 37866 5 13181 6 33418 7 31611 8 9600 9 47851 10 22729 11 34920 12 20679 13 13874 14 35815 15 1308 16 40327 17 20697 18 34642 19 45144 20 40726 21 36899 22 49440 23 42507 24 34983 25 34496 26 41651 27 19121 28 30392 29 48080 30 18302 31 28030 32 22472 33 26275 34 17680 3...
output:
177 25075 32138 400 36791 38592 28612 12464 10352 43337 36452 43158 13659 5593 29988 23224 7087 23922 25697 21833 5923 44766 33658 16893 26217 30297 37628 43546 12097 2042 26157 34289 36173 22194 3792 36001 44332 6645 23987 19246 32699 8178 25580 8650 32659 39845 21279 24361 32241 26532 20586 3931 3...
result:
ok 49996 numbers
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%