QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#454998 | #7769. Axium Crisis | kkkgjyismine4 | 80 | 8487ms | 68320kb | C++23 | 4.7kb | 2024-06-25 17:28:17 | 2024-06-25 17:28:17 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
using namespace std;
mt19937 rnd(time(0));
int dep[100500],son[100500][2],tot,rt,n;
pii ans[100500];
int id[100500],len[100500],Mask[100500],tt,fa[100500];
vector<pii>road[20];
vector<int>vec[100500];
vector<pii>Vec[100500];
map<pii,int>Mp;
int Rt;
const int inf=1e9;
int f[1<<17][20],d[1<<17][20];
struct Node{int pos,mask,lcp,Preval,lstd;}stk[50005000];
int tail;
void dfs(int u,int f,int p,int d,int m){
if(p>rt)vec[p].pb(m),Vec[p].pb(mp(Rt,u));
for(auto v:road[u]){
if(v.fi==f)continue;
int id1=Mp[mp(u,v.fi)];
if(u>v.fi)id1=Mp[mp(v.fi,u)];
if(v.se<2){
if(!son[p][v.se])son[p][v.se]=++tot,dep[tot]=dep[p]+1;
dfs(v.fi,u,son[p][v.se],d+1,(m|(1<<id1-1)));
}else{
if(d<2){
if(!son[p][0])son[p][0]=++tot,dep[tot]=dep[p]+1;
if(!son[p][1])son[p][1]=++tot,dep[tot]=dep[p]+1;
dfs(v.fi,u,son[p][0],d+1,(m|(1<<id1-1)));
dfs(v.fi,u,son[p][1],d+1,(m|(1<<id1-1)));
}else{
int o=rnd()%2;
if(!son[p][o])son[p][o]=++tot,dep[tot]=dep[p]+1;
dfs(v.fi,u,son[p][o],d+1,(m|(1<<id1-1)));
}
}
}
}
void Dfs(int p){
for(int i=0;i<vec[p].size();++i){
auto v=vec[p][i];id[++tt]=p,len[tt]=dep[p],Mask[tt]=v;
ans[tt]=Vec[p][i];
}
if(son[p][0])Dfs(son[p][0]);
if(son[p][1])Dfs(son[p][1]);
}
int LCP(int p,int q){
if(dep[p]>dep[q])swap(p,q);
while(dep[q]>dep[p])q=fa[q];
while(p!=q)p=fa[p],q=fa[q];
return dep[p];
}
int ht[20505];
int opr(int x){return son[fa[x]][1]==x;}
int Stk[20],Tail,pw[20];
int stk1[20],tail1;
void dfs1(int u,int f,int t){
if(tail1==-1)return;
stk1[++tail1]=u;
if(u==t){
for(int i=tail1-1;i>=1;--i)pw[Mp[mp(min(stk1[i],stk1[i+1]),max(stk1[i],stk1[i+1]))]]=Stk[i];
tail1=-1;
return;
}
for(auto v:road[u]){
if(tail1==-1)break;
if(v.fi==f)continue;
dfs1(v.fi,u,t);
}
if(tail1==-1)return;
--tail1;
}
void solve(){
scanf("%d",&n),Mp.clear();int tt1=0;
for(int i=1;i<=n;++i)road[i].clear();
for(int i=1;i<n;++i){
int u,v,w;scanf("%d%d%d",&u,&v,&w),pw[i]=w;++u,++v;
if(u>v)swap(u,v);Mp[mp(u,v)]=++tt1;
road[u].pb(mp(v,w)),road[v].pb(mp(u,w));
}
for(int i=1;i<=tot;++i)son[i][0]=son[i][1]=dep[i]=fa[i]=id[i]=0,vec[i].clear(),Vec[i].clear();
tot=rt=1,tt=0;
for(int i=1;i<=n;++i)Rt=i,dfs(i,-1,rt,0,0);
for(int i=1;i<=tot;++i){
if(son[i][0])fa[son[i][0]]=i;
if(son[i][1])fa[son[i][1]]=i;
}
Dfs(rt);
for(int i=0;i<(1<<n-1);++i)for(int j=0;j<=n-1;++j)f[i][j]=-inf,d[i][j]=0;
f[0][0]=0,tail=0;
int Ans=-inf,D=0,ed=tt;
for(int i=1;i<tt;++i)ht[i]=LCP(id[i],id[i+1]);
for(int i=1;i<=tt;++i){
int Val=len[i];if(i>1)Val=ht[i-1];
for(int jk=i-1,mn=len[jk];jk>=1&&mn>Val;mn=min(mn,ht[jk-1]),--jk){
int now=(((1<<n-1)-1)^Mask[jk]);
for(int s=now;;s=((s-1)&now)){
int j=(s|Mask[jk]);
int mx=-inf,from=-1;
for(int k=Val;k<n;++k){
if(f[j][k]<0)continue;
if(f[j][k]>mx)mx=f[j][k],from=k;
}
if(mx>f[j][Val]){
stk[++tail]=Node{2*i-1,j,Val,f[j][Val],d[j][Val]};
f[j][Val]=mx,d[j][Val]=from;
}
if(!s)break;
}
}
for(int j=0;j<(1<<n-1);++j){
if(j&Mask[i])continue;
int Mx=-inf,Now=-1;
for(int k=0;k<n;++k){
int res=f[j][k]-k+len[i];
if(res<0)continue;
Mx=max(Mx,res);
if(Mx==res)Now=k;
}
if(f[j|Mask[i]][len[i]]<Mx){
stk[++tail]=Node{2*i,(j|Mask[i]),len[i],f[j|Mask[i]][len[i]],d[j|Mask[i]][len[i]]};
f[j|Mask[i]][len[i]]=Mx,d[j|Mask[i]][len[i]]=Now;
}
}
int ans=0;
for(int j=0;j<n;++j)ans=max(ans,f[(1<<n-1)-1][j]);
if(ans==n-1){ed=i;break;}
}
for(int i=0;i<n;++i)
if(Ans<f[(1<<n-1)-1][i])
Ans=f[(1<<n-1)-1][i],D=i;
printf("%d\n",Ans+1);
/* int Now=(1<<n-1)-1;
vector<int>Res;
for(int i=ed;i>=1;--i){
while(tail&&stk[tail].pos==2*i){
f[stk[tail].mask][stk[tail].lcp]=stk[tail].Preval;
d[stk[tail].mask][stk[tail].lcp]=stk[tail].lstd;
--tail;
}
Tail=0;
for(int j=id[i];j>rt;j=fa[j])Stk[++Tail]=opr(j);
reverse(Stk+1,Stk+Tail+1);
if((Now&Mask[i])==Mask[i]&&D==len[i]){
for(int k=0;k<n;++k)
if(f[Now^Mask[i]][k]-k+len[i]==Ans){
Now^=Mask[i],D=k,Ans=f[Now][D],Res.pb(i);
Rt=ans[i].fi,tail1=0,dfs1(ans[i].fi,-1,ans[i].se);
break;
}
}
while(tail&&stk[tail].pos==2*i-1){
f[stk[tail].mask][stk[tail].lcp]=stk[tail].Preval;
d[stk[tail].mask][stk[tail].lcp]=stk[tail].lstd;
--tail;
}
while(f[Now][D]<Ans)++D;
}
printf("%d\n",Res.size());
for(int i=1;i<n;++i)printf("%d ",min(pw[i],1));
puts("");
for(auto v:Res)printf("%d %d\n",ans[v].fi-1,ans[v].se-1);*/
}
int main(){
puts("0");
int T,o;cin>>T>>o;
while(T--)solve();
return 0;
}
詳細信息
Subtask #1:
score: 8
Acceptable Answer
Test #1:
score: 8
Acceptable Answer
time: 3ms
memory: 12176kb
input:
1000 0 4 0 2 0 2 3 0 2 1 0 4 3 2 1 0 2 1 1 2 2 4 0 2 2 0 1 0 3 0 0 4 1 2 1 3 2 0 2 0 1 4 0 2 0 0 3 0 2 1 0 4 0 2 1 0 3 1 0 1 1 4 3 1 0 2 1 2 3 0 2 4 3 1 1 3 0 1 2 3 0 4 1 0 0 2 0 2 2 3 2 4 1 2 0 3 0 0 2 3 2 3 2 1 0 0 2 1 4 3 0 1 1 2 1 2 3 0 4 2 1 0 3 0 1 1 0 1 4 3 2 1 3 1 1 0 1 1 4 1 2 1 1 3 0 3 0 1...
output:
0 3 4 4 4 4 3 4 4 4 4 3 4 4 4 4 4 4 4 3 4 4 3 4 4 4 3 4 4 4 4 3 4 4 3 4 4 4 4 4 4 4 3 4 4 3 4 4 4 4 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 4 3 4 4 3 4 4 2 4 4 3 3 4 3 3 4 4 3 4 3 4 4 4 4 4 4 3 4 4 4 4 4 4 4 4 4 4 4 3 4 3 4 4 3 4 3 4 4 4 4 3 4 4 4 4 3 4 4 4 3 4 4 4 4 4 4 4 4 3 4 4 4 3 4 4 4 4 4 3 4 4 ...
result:
points 0.80 Partially Accepted. You Got 80% score.
Test #2:
score: 8
Acceptable Answer
time: 0ms
memory: 10144kb
input:
1000 0 4 2 0 0 2 1 0 0 3 0 4 2 1 0 2 0 0 1 3 0 4 1 3 0 1 0 0 2 1 0 4 0 1 2 2 1 2 1 3 2 4 0 2 2 3 2 0 1 3 1 4 1 3 0 2 3 0 3 0 0 4 1 2 1 3 0 0 0 2 0 4 3 2 1 2 1 1 0 1 0 4 2 1 0 3 2 0 2 0 0 4 1 3 0 2 3 0 3 0 2 4 2 0 0 3 0 1 1 2 1 4 0 2 2 3 1 2 2 1 2 4 1 3 2 3 0 2 2 0 2 4 2 0 0 2 1 2 2 3 1 4 0 1 2 2 3 1...
output:
0 4 4 3 4 4 3 4 4 3 4 4 4 4 4 4 3 4 4 4 4 4 4 4 4 3 4 3 4 4 4 4 4 4 4 4 4 4 4 3 4 4 4 3 4 4 4 4 4 3 4 4 4 4 4 4 3 4 3 3 4 3 4 3 4 4 4 4 3 4 4 4 4 3 4 3 4 4 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 4 4 3 4 4 3 4 4 4 4 4 4 4 4 4 4 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 4 4 4 ...
result:
points 0.80 Partially Accepted. You Got 80% score.
Subtask #2:
score: 8
Acceptable Answer
Test #3:
score: 8
Acceptable Answer
time: 7ms
memory: 12204kb
input:
3000 3 4 0 1 1 0 3 1 0 2 0 4 3 2 0 0 1 1 1 2 0 4 1 0 0 2 3 1 3 1 0 4 2 1 0 2 0 1 3 0 0 4 2 3 1 3 0 1 2 1 0 4 2 3 1 2 1 1 2 0 1 4 0 2 0 1 0 0 3 0 0 4 3 1 1 0 2 0 2 3 0 6 4 0 0 3 1 1 2 3 0 0 5 1 1 5 0 4 2 3 1 3 0 0 3 1 1 4 0 3 0 1 2 0 0 2 1 4 0 2 1 3 1 0 2 1 1 4 2 0 0 2 3 1 1 3 0 6 3 1 0 3 4 1 4 0 1 2...
output:
0 4 4 4 4 4 3 3 4 6 4 4 4 4 5 4 4 3 3 4 5 3 3 4 4 5 4 3 4 4 4 3 3 5 4 4 4 4 3 3 4 4 4 5 4 4 4 4 3 4 6 4 4 6 4 4 4 4 4 3 5 4 4 4 3 4 6 4 3 3 4 4 4 4 6 4 3 4 3 4 3 3 4 4 6 4 4 6 3 6 4 4 5 4 4 4 3 3 4 6 4 4 4 6 4 4 3 4 3 4 3 6 3 4 6 4 3 4 6 3 6 4 6 4 4 4 3 7 4 4 4 3 4 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 ...
result:
points 0.80 Partially Accepted. You Got 80% score.
Test #4:
score: 8
Acceptable Answer
time: 10ms
memory: 12116kb
input:
3000 3 3 0 1 0 1 2 0 4 2 1 1 0 2 0 0 3 1 6 3 4 1 1 4 0 1 5 1 2 1 1 3 0 0 4 0 2 1 1 2 0 1 3 1 4 0 3 1 2 0 1 1 2 0 6 1 2 0 0 3 0 2 5 0 0 2 1 4 2 0 4 2 0 0 2 1 1 3 1 1 4 1 0 1 1 2 0 3 0 1 4 1 3 0 2 1 1 0 2 0 4 1 3 0 2 1 0 1 0 0 4 3 1 0 2 3 0 0 1 1 4 1 0 0 2 0 0 3 0 0 4 2 1 1 1 0 1 2 3 0 4 3 0 1 1 0 0 2...
output:
0 3 4 6 4 4 5 4 4 4 3 4 3 4 4 6 4 4 4 4 4 6 4 6 3 4 3 3 4 3 4 3 3 4 3 4 4 4 4 6 4 6 4 4 4 4 3 4 4 4 4 6 6 3 3 3 4 4 4 4 4 4 5 4 4 4 4 3 3 4 4 4 4 4 4 4 4 3 5 4 4 4 3 4 4 4 4 4 4 4 3 4 4 6 4 4 4 4 4 4 6 4 4 4 4 6 3 6 3 5 4 3 4 5 6 4 4 4 4 4 3 4 3 4 3 4 6 4 3 4 4 4 4 4 4 4 4 4 4 4 6 4 4 4 4 4 4 3 4 4 ...
result:
points 0.80 Partially Accepted. You Got 80% score.
Subtask #3:
score: 8
Acceptable Answer
Dependency #1:
80%
Acceptable Answer
Dependency #2:
80%
Acceptable Answer
Test #5:
score: 8
Acceptable Answer
time: 29ms
memory: 12248kb
input:
3000 4 4 2 0 0 1 2 0 1 3 0 4 1 2 2 0 2 2 3 2 2 4 3 1 2 3 2 0 0 2 0 4 0 3 2 2 1 2 0 1 2 4 0 1 0 3 0 0 0 2 2 4 2 0 0 2 1 0 3 0 0 6 0 3 2 5 0 2 5 2 2 1 4 2 4 3 2 4 0 3 0 3 1 0 0 2 0 4 1 0 2 2 0 2 3 2 2 4 2 1 2 1 0 2 0 3 2 6 5 0 2 0 2 2 0 4 2 1 0 2 0 3 2 6 4 5 2 0 1 2 0 3 2 4 3 2 5 2 2 4 1 3 0 3 2 0 1 0...
output:
0 4 4 4 4 4 4 6 4 4 4 5 6 4 6 4 4 4 4 4 4 4 3 4 6 5 6 4 4 4 6 6 4 4 4 4 4 3 3 5 6 4 6 4 4 4 4 4 3 4 3 4 6 6 3 5 4 4 5 5 6 4 8 4 3 5 4 6 4 3 3 4 4 4 4 5 4 4 4 6 4 6 4 6 3 4 3 3 3 6 4 4 6 6 4 4 4 8 4 6 4 5 4 4 6 3 4 3 4 5 3 5 8 4 6 6 6 3 3 3 6 4 4 4 4 4 6 3 4 6 4 3 3 6 4 4 6 3 4 6 4 4 5 4 5 4 4 6 3 4 ...
result:
points 0.80 Partially Accepted. You Got 80% score.
Test #6:
score: 8
Acceptable Answer
time: 26ms
memory: 10252kb
input:
3000 0 6 1 3 2 0 4 0 1 4 2 3 5 1 0 2 0 6 0 5 0 0 4 1 0 2 0 3 0 0 1 0 0 6 4 1 2 2 1 1 5 0 2 5 3 1 2 3 0 4 2 0 0 1 0 2 1 3 0 4 2 3 1 0 1 1 2 1 0 4 0 3 1 1 0 2 2 3 0 4 1 3 1 2 3 0 0 1 2 6 1 0 1 4 1 1 5 1 1 3 1 1 2 1 2 4 0 3 1 1 3 2 1 2 1 4 1 2 1 0 2 0 3 1 1 6 0 2 1 1 2 1 0 5 0 2 4 1 2 3 1 6 3 2 1 0 2 0...
output:
0 6 5 6 4 4 4 4 5 4 4 6 6 4 4 6 3 3 3 5 5 4 4 4 4 4 5 3 6 4 4 4 3 6 6 4 4 4 4 4 6 4 3 4 6 5 4 5 3 4 4 4 4 4 6 8 3 4 6 6 4 4 3 4 4 4 4 5 4 3 3 5 6 4 4 4 6 6 4 4 4 6 3 4 4 4 4 4 4 5 6 6 4 4 4 3 6 4 6 5 4 4 3 4 4 3 4 3 4 3 4 4 3 4 6 4 4 4 4 6 4 4 6 4 6 3 4 4 5 3 6 6 4 4 4 4 4 4 11 4 4 6 4 5 4 5 6 6 4 3...
result:
points 0.80 Partially Accepted. You Got 80% score.
Subtask #4:
score: 8
Acceptable Answer
Dependency #2:
80%
Acceptable Answer
Test #7:
score: 8
Acceptable Answer
time: 150ms
memory: 15384kb
input:
3000 3 8 1 2 1 3 7 0 7 0 1 7 4 0 6 5 0 6 4 1 2 0 0 5 3 1 0 3 2 1 0 1 0 4 0 1 5 3 2 0 4 0 0 4 1 0 2 0 1 6 5 4 1 4 1 1 4 2 1 0 4 1 4 3 1 5 4 1 0 4 3 0 2 1 1 3 0 1 8 3 6 0 1 4 1 2 3 1 0 6 1 0 7 1 2 1 0 7 5 0 8 4 5 0 5 7 0 3 0 0 2 4 1 1 2 0 5 6 0 6 3 1 5 4 1 0 4 0 0 4 3 0 2 4 1 5 1 0 0 1 2 0 2 3 1 0 4 1...
output:
0 8 5 5 3 5 8 7 5 5 6 6 5 8 6 6 7 5 6 6 6 6 6 6 5 5 6 5 8 8 6 5 6 6 8 4 6 8 7 7 6 8 5 6 5 5 3 8 8 5 7 6 8 6 7 6 6 8 8 5 5 8 6 6 5 7 6 5 6 6 5 6 7 6 6 7 5 6 8 7 6 7 6 6 7 6 6 5 8 6 6 6 6 5 5 5 5 7 5 8 6 5 5 6 8 6 6 8 7 6 6 8 5 6 8 7 7 14 8 5 6 5 6 7 5 8 6 5 6 6 7 6 3 5 7 8 8 6 9 8 6 6 8 14 5 4 6 5 6 ...
result:
points 0.80 Partially Accepted. You Got 80% score.
Test #8:
score: 8
Acceptable Answer
time: 165ms
memory: 14656kb
input:
3000 3 6 3 1 1 1 4 0 1 0 1 1 2 0 5 1 0 6 0 3 1 2 4 1 1 5 1 1 4 0 4 0 0 6 2 5 0 1 5 1 3 4 0 4 0 0 3 2 1 8 2 5 0 6 7 0 0 3 0 6 0 1 1 4 0 7 5 1 3 4 1 11 7 6 1 3 5 1 2 7 1 7 10 0 1 7 0 8 7 0 9 7 0 4 7 0 5 7 0 0 7 1 6 5 1 1 2 4 1 3 0 1 2 0 0 5 4 0 8 3 1 1 1 6 0 0 7 0 2 7 1 4 5 1 4 3 1 0 6 1 6 0 2 0 1 2 0...
output:
0 5 6 6 8 8 6 8 5 6 6 6 5 6 7 5 7 6 7 5 8 7 5 7 6 6 7 5 6 6 5 6 8 6 8 5 5 5 7 7 5 7 6 5 8 6 8 3 6 5 5 6 7 3 5 3 6 6 6 8 6 5 5 8 6 5 6 5 6 7 6 6 6 7 5 5 8 5 6 5 6 8 6 6 5 6 5 4 5 4 8 7 5 6 6 6 8 8 6 5 6 5 8 6 7 6 8 6 5 8 6 8 7 7 8 5 8 7 6 3 7 7 8 6 8 8 6 7 5 5 5 8 5 6 5 6 5 6 7 5 8 5 4 7 6 5 8 5 8 6 ...
result:
points 0.80 Partially Accepted. You Got 80% score.
Subtask #5:
score: 8
Acceptable Answer
Dependency #3:
80%
Acceptable Answer
Dependency #4:
80%
Acceptable Answer
Test #9:
score: 8
Acceptable Answer
time: 290ms
memory: 14812kb
input:
3000 4 6 2 5 2 3 4 0 2 1 0 0 1 0 0 3 2 6 2 0 2 1 4 0 5 3 0 0 4 2 0 3 0 8 4 6 2 2 5 2 1 0 2 5 0 2 1 4 2 4 7 2 3 7 2 6 0 4 0 5 2 0 2 1 0 1 0 2 5 3 2 8 5 6 2 6 3 2 6 7 2 7 4 2 2 6 2 1 4 2 0 4 2 6 1 5 0 2 1 0 3 1 0 5 0 0 2 4 0 6 5 1 2 0 5 0 2 4 2 2 5 0 4 3 0 8 7 6 0 6 1 0 2 0 0 7 3 0 3 2 0 4 0 0 5 1 0 6...
output:
0 6 6 8 6 7 5 6 8 6 5 8 8 6 6 4 8 9 6 6 6 6 8 5 6 6 6 8 7 4 8 8 6 6 6 6 8 5 4 6 8 8 8 6 8 7 7 5 6 3 6 6 8 8 5 5 7 5 6 6 6 7 3 7 5 7 4 6 6 7 3 5 4 5 6 6 4 6 4 6 7 5 6 6 6 6 9 5 3 5 5 6 8 8 3 4 4 6 6 6 8 5 14 6 6 8 8 8 6 4 5 6 6 6 5 5 5 8 6 4 6 6 8 4 6 4 5 6 6 5 4 4 6 4 3 6 8 4 6 6 5 4 6 6 8 5 5 6 5 6...
result:
points 0.80 Partially Accepted. You Got 80% score.
Test #10:
score: 8
Acceptable Answer
time: 188ms
memory: 15308kb
input:
3000 0 6 4 0 0 1 4 1 5 3 0 3 2 1 0 5 1 8 1 7 0 6 1 0 4 2 0 4 1 1 5 4 0 4 3 0 0 4 1 8 3 1 0 2 3 0 3 0 0 4 7 0 5 7 0 7 6 0 7 3 0 6 5 2 2 4 0 2 0 3 2 5 4 2 1 3 2 4 2 3 1 3 0 1 1 3 1 5 0 2 1 2 4 0 1 4 2 3 4 0 6 1 0 0 4 2 0 4 5 0 3 5 0 2 0 0 5 0 1 0 0 2 0 0 3 0 0 4 0 6 1 4 1 1 3 1 1 5 1 0 2 0 1 2 0 5 0 2...
output:
0 6 6 4 6 3 5 6 3 6 5 5 6 5 8 6 6 5 3 8 5 8 8 6 4 6 6 5 7 5 5 5 6 6 5 5 8 6 6 5 8 6 6 6 5 6 7 4 7 6 8 8 5 8 7 6 6 5 7 5 8 3 8 6 6 6 6 6 6 6 5 6 6 8 6 6 5 8 8 8 6 5 8 6 5 6 6 5 5 6 6 8 6 4 8 5 7 8 8 7 7 6 6 5 8 8 7 7 5 5 6 6 5 7 3 6 5 5 7 8 5 6 7 6 5 5 8 8 6 8 5 6 8 5 5 7 5 4 5 3 6 6 6 8 5 5 6 5 8 6 ...
result:
points 0.80 Partially Accepted. You Got 80% score.
Subtask #6:
score: 8
Acceptable Answer
Dependency #4:
80%
Acceptable Answer
Test #11:
score: 8
Acceptable Answer
time: 1166ms
memory: 29720kb
input:
3000 3 8 3 5 1 4 1 0 4 6 1 5 6 0 7 5 0 3 2 1 3 0 1 8 1 4 1 0 3 0 7 3 1 5 2 1 5 3 1 5 1 0 6 0 1 8 1 4 1 1 2 1 0 1 0 6 7 1 3 5 1 6 4 0 4 5 0 8 7 0 0 1 4 0 3 1 1 4 2 1 2 6 0 4 5 0 7 3 1 8 7 0 0 5 7 1 4 2 0 1 3 0 2 5 0 6 0 0 3 0 1 8 1 3 0 3 4 0 6 3 1 7 5 1 3 0 0 7 3 0 5 2 0 5 1 3 0 3 0 1 1 2 1 2 4 0 8 5...
output:
0 7 7 7 8 8 7 5 7 4 7 7 5 5 7 7 8 6 6 6 6 8 7 11 6 7 6 5 6 8 8 6 6 6 6 8 8 7 8 8 7 6 5 6 8 7 9 14 8 5 8 7 8 5 8 6 7 7 5 5 5 7 7 5 7 6 8 6 6 5 6 7 8 8 7 5 4 6 7 7 3 8 6 8 8 6 8 8 7 8 5 11 8 6 8 7 8 11 7 8 6 8 6 7 11 8 6 8 7 5 8 7 10 8 6 3 6 11 8 6 8 9 3 7 8 6 6 7 7 8 7 5 11 7 3 6 6 8 8 8 6 10 7 7 8 6...
result:
points 0.80 Partially Accepted. You Got 80% score.
Test #12:
score: 8
Acceptable Answer
time: 1130ms
memory: 29708kb
input:
3000 3 8 4 5 1 6 4 0 3 7 1 1 6 1 0 2 1 5 7 0 1 2 0 8 6 1 1 1 4 0 6 7 0 6 0 1 2 1 1 6 3 0 5 0 1 8 1 0 0 7 3 0 1 4 0 2 1 0 6 5 0 3 4 1 5 2 1 8 0 4 1 5 2 1 3 0 0 7 0 1 0 2 0 0 1 1 6 3 1 7 3 6 1 1 0 0 0 4 1 5 2 1 5 4 0 5 6 0 8 0 1 1 7 4 0 1 2 1 0 6 0 4 5 0 6 3 1 1 4 1 11 1 3 0 3 0 0 3 5 1 8 3 0 9 8 1 3 ...
output:
0 8 7 7 7 7 7 8 8 8 7 7 10 5 8 5 7 7 7 5 7 7 8 7 8 6 7 8 8 8 6 7 8 8 10 5 6 7 7 8 7 7 8 8 6 8 8 7 7 8 8 5 8 7 7 6 8 7 6 7 11 5 7 7 8 8 3 6 6 8 5 5 8 9 6 7 6 8 10 8 6 14 5 8 8 8 6 6 6 7 7 6 8 5 8 7 6 3 7 7 6 8 8 7 7 8 9 8 5 5 6 8 7 7 7 7 5 8 5 7 7 6 6 8 11 8 5 8 8 5 7 5 6 6 7 8 7 8 5 6 7 7 8 7 7 11 3...
result:
points 0.80 Partially Accepted. You Got 80% score.
Subtask #7:
score: 4
Acceptable Answer
Test #13:
score: 4
Acceptable Answer
time: 1483ms
memory: 39596kb
input:
3000 1 11 2 5 0 10 2 0 6 2 0 2 8 0 0 2 0 2 1 0 2 4 0 2 9 0 2 3 0 7 2 0 11 7 8 0 6 4 0 1 6 0 2 8 0 8 0 0 6 3 0 9 5 0 5 8 0 1 2 0 9 10 0 8 1 4 0 2 3 0 6 5 0 6 7 0 2 4 0 7 3 0 1 0 0 8 4 0 0 0 5 0 7 2 0 0 2 0 0 6 0 0 1 0 0 3 0 11 5 1 0 7 2 0 9 2 0 4 9 0 0 2 0 8 5 0 0 6 0 3 6 0 4 10 0 1 7 0 7 6 2 0 0 5 0...
output:
0 3 8 8 4 8 7 5 7 11 4 8 4 8 10 5 6 7 5 3 11 6 9 6 6 8 8 5 6 4 5 11 4 5 9 6 9 8 8 4 4 8 11 8 6 4 8 7 4 11 7 7 6 7 8 8 8 6 4 8 8 7 7 8 11 8 5 8 4 7 5 7 7 4 6 5 8 5 3 5 8 7 8 5 8 4 5 4 5 4 6 8 5 6 5 5 5 7 5 8 7 6 3 7 7 8 7 5 4 5 5 4 11 6 8 7 6 5 3 6 6 7 8 8 4 6 5 3 3 8 3 7 7 5 7 3 11 3 4 8 6 4 5 4 5 6...
result:
points 0.80 Partially Accepted. You Got 80% score.
Subtask #8:
score: 12
Acceptable Answer
Test #14:
score: 12
Acceptable Answer
time: 8230ms
memory: 65956kb
input:
3000 2 8 4 7 2 4 3 2 3 2 2 4 5 2 1 4 2 6 4 2 0 1 2 8 1 5 2 0 7 2 3 2 2 3 1 2 5 7 2 4 0 2 6 4 2 8 1 3 2 5 3 2 7 6 2 2 6 2 0 7 2 4 6 2 0 5 2 8 5 7 2 2 6 2 1 6 2 4 5 2 4 0 2 0 1 2 7 3 2 11 2 7 2 0 9 2 8 9 2 10 7 2 6 9 2 9 3 2 4 10 2 7 5 2 7 9 2 1 9 2 8 2 6 2 1 5 2 4 1 2 1 3 2 6 1 2 0 1 2 6 7 2 14 2 6 2...
output:
0 7 8 8 8 9 6 7 6 6 10 8 7 6 6 9 6 7 8 11 8 9 8 8 8 6 7 7 11 6 5 7 8 8 7 6 9 7 7 11 8 7 8 6 7 10 6 8 6 7 7 7 7 8 7 9 11 8 7 7 7 11 8 8 7 6 6 7 8 7 8 7 6 7 8 7 11 11 6 7 7 8 8 7 6 8 8 8 9 7 7 8 6 7 7 7 11 6 7 6 8 8 8 8 7 5 6 7 6 7 7 7 8 6 8 8 5 7 8 7 6 7 8 7 6 7 11 10 8 7 8 8 6 6 11 7 7 11 7 10 7 9 7...
result:
points 0.80 Partially Accepted. You Got 80% score.
Test #15:
score: 12
Acceptable Answer
time: 8012ms
memory: 68320kb
input:
3000 2 8 0 5 2 2 6 2 2 3 2 4 3 2 1 5 2 1 6 2 7 4 2 8 2 3 2 1 5 2 6 7 2 1 4 2 6 0 2 2 5 2 3 7 2 7 4 3 2 0 6 2 6 1 2 2 4 2 4 5 2 5 6 2 6 2 0 2 1 2 2 2 4 2 4 3 2 2 5 2 7 6 4 2 1 4 2 5 4 2 3 6 2 0 2 2 4 2 2 8 3 4 2 6 3 2 2 3 2 5 3 2 0 7 2 3 0 2 1 3 2 8 1 5 2 1 2 2 2 4 2 1 6 2 0 1 2 7 1 2 3 2 2 8 7 5 2 7...
output:
0 8 8 6 6 7 7 6 8 11 8 8 8 6 6 8 9 8 8 8 7 5 11 8 6 8 8 11 6 8 7 8 14 10 8 7 8 7 8 7 6 7 8 8 7 6 6 9 4 7 8 7 10 6 7 8 11 8 8 7 8 8 7 7 10 5 6 7 6 7 13 8 6 7 8 8 7 8 6 11 8 7 11 10 10 11 7 7 5 8 8 8 8 7 8 7 6 10 7 6 5 8 7 7 6 7 6 10 7 8 7 8 6 6 7 6 7 8 8 5 8 8 9 8 7 5 6 7 6 8 7 8 10 6 7 8 7 5 7 8 8 8...
result:
points 0.80 Partially Accepted. You Got 80% score.
Test #16:
score: 12
Acceptable Answer
time: 8487ms
memory: 68112kb
input:
3000 2 8 7 2 2 5 2 2 4 2 2 0 2 2 6 2 2 1 2 2 3 2 2 8 6 4 2 4 7 2 0 4 2 3 2 2 3 4 2 5 3 2 5 1 2 8 0 1 2 4 0 2 3 2 2 6 7 2 6 2 2 5 3 2 7 1 2 10 3 1 2 8 3 2 7 3 2 4 3 2 2 3 2 9 3 2 0 3 2 6 3 2 3 5 2 7 2 5 2 3 2 2 5 0 2 2 1 2 6 2 2 4 2 2 8 2 7 2 2 6 2 2 5 2 2 4 2 0 2 2 2 3 2 2 1 2 7 5 2 2 1 5 2 4 2 2 3 ...
output:
0 6 7 8 7 6 6 7 6 8 7 8 7 8 6 8 6 8 7 7 11 8 8 10 8 5 7 7 7 11 8 8 11 8 7 7 8 7 8 7 6 9 8 6 7 8 7 7 8 6 8 6 8 9 8 8 8 7 8 8 11 7 7 8 7 8 7 8 9 7 7 7 7 8 7 7 6 15 7 10 7 8 7 8 11 6 7 8 6 10 6 6 6 7 8 8 8 6 11 11 7 8 7 9 8 6 6 7 8 7 8 11 7 10 10 10 11 6 7 8 7 8 7 13 6 7 7 8 10 8 7 7 8 7 8 9 8 10 8 8 8...
result:
points 0.80 Partially Accepted. You Got 80% score.
Subtask #9:
score: 8
Acceptable Answer
Dependency #6:
80%
Acceptable Answer
Dependency #7:
80%
Acceptable Answer
Test #17:
score: 8
Acceptable Answer
time: 2419ms
memory: 46232kb
input:
3000 3 8 1 2 0 4 6 1 2 4 1 3 4 1 4 0 0 5 6 0 4 7 1 8 6 0 0 2 6 1 5 4 1 0 4 1 2 3 0 7 1 1 5 1 0 17 8 7 0 15 7 0 5 7 1 4 5 1 2 5 1 16 5 1 10 16 0 14 5 1 6 2 0 3 5 1 12 7 0 14 0 0 3 1 0 9 5 1 13 5 1 16 11 0 14 4 3 0 2 10 1 12 1 0 9 7 0 6 13 0 5 11 0 8 12 1 6 3 1 4 1 1 0 10 0 2 8 0 7 5 1 0 11 1 8 7 6 0 ...
output:
0 7 8 10 14 7 7 8 7 8 8 8 3 8 7 6 7 7 7 7 7 11 9 9 8 8 7 8 3 8 7 6 9 8 7 7 7 11 6 6 8 7 8 6 8 8 11 5 6 6 8 5 8 8 8 6 7 8 6 8 10 3 8 8 7 6 7 8 8 7 7 7 10 8 8 8 7 8 7 8 8 8 7 8 14 6 7 7 8 5 8 6 6 7 7 6 7 7 8 5 6 8 5 10 3 8 6 8 8 7 5 7 7 8 7 6 8 7 13 8 7 7 7 4 8 5 7 8 8 6 10 7 5 7 6 8 9 9 7 8 6 3 7 7 7...
result:
points 0.80 Partially Accepted. You Got 80% score.
Test #18:
score: 8
Acceptable Answer
time: 2497ms
memory: 46428kb
input:
3000 3 8 2 7 0 3 4 0 1 0 0 7 5 1 2 3 1 6 5 0 0 4 1 11 10 5 1 2 5 1 5 9 0 5 0 0 4 1 0 3 5 0 5 1 1 6 5 0 7 5 0 8 1 1 8 3 4 1 1 3 1 7 3 0 5 3 0 5 2 0 6 0 0 0 2 1 7 2 5 1 1 3 1 1 5 0 0 6 1 0 2 0 6 4 0 7 0 3 0 2 6 1 0 4 1 5 1 1 4 6 0 1 3 1 11 1 4 0 9 4 0 10 4 1 4 2 0 7 4 0 7 6 1 4 5 0 8 4 1 4 0 0 4 3 1 6...
output:
0 8 8 8 7 7 8 6 7 11 7 7 7 6 5 11 5 8 7 7 8 7 8 8 15 8 6 7 7 7 8 8 8 8 7 7 7 8 8 8 8 5 5 7 7 7 7 8 6 6 11 8 5 8 7 11 8 7 8 5 8 6 7 7 8 8 7 7 7 7 8 8 6 5 11 11 8 12 7 8 8 6 8 8 7 8 7 7 7 7 7 14 11 9 12 7 7 7 9 7 14 8 8 7 7 8 7 11 7 7 7 7 6 8 7 6 7 6 5 6 7 7 5 6 5 11 8 7 8 5 7 7 6 7 5 4 5 5 4 5 7 7 8 ...
result:
points 0.80 Partially Accepted. You Got 80% score.
Subtask #10:
score: 8
Acceptable Answer
Dependency #5:
80%
Acceptable Answer
Dependency #8:
80%
Acceptable Answer
Dependency #9:
80%
Acceptable Answer
Test #19:
score: 8
Acceptable Answer
time: 3702ms
memory: 48204kb
input:
3000 0 8 3 2 0 0 2 1 4 1 1 5 4 0 3 6 1 7 5 1 6 1 0 8 3 1 2 4 5 0 1 6 2 5 0 0 3 2 0 7 5 2 2 4 0 8 4 7 1 5 3 0 4 0 1 6 5 1 3 1 2 2 4 1 3 4 2 11 3 2 0 8 2 0 1 5 2 0 8 2 3 9 2 0 7 2 4 3 0 6 9 2 6 5 0 10 9 2 11 10 1 2 8 4 2 8 7 2 0 4 2 8 6 2 3 9 2 2 9 2 2 1 2 0 3 2 5 8 2 7 3 5 0 0 3 1 4 2 0 5 2 1 1 4 1 1...
output:
0 8 8 7 10 11 7 8 8 7 7 5 7 8 6 8 6 6 5 8 7 13 9 7 6 7 9 5 16 7 6 8 6 8 7 7 5 8 7 8 7 8 11 8 7 5 11 11 7 14 7 6 3 7 7 12 7 6 7 7 7 5 8 7 6 7 6 7 9 10 6 5 6 8 7 7 6 6 7 6 4 11 11 8 7 7 7 5 7 8 8 7 7 7 11 6 8 6 8 5 4 7 7 5 8 8 8 8 7 8 5 8 8 8 8 7 4 8 8 8 8 10 11 6 7 10 7 8 6 7 11 8 5 7 8 7 9 7 8 7 9 7...
result:
points 0.80 Partially Accepted. You Got 80% score.
Test #20:
score: 8
Acceptable Answer
time: 3432ms
memory: 54772kb
input:
3000 0 8 0 3 0 7 1 0 0 5 0 1 4 0 2 5 0 6 2 0 4 6 0 8 1 5 0 6 0 1 2 3 1 5 7 1 4 1 1 6 4 0 3 0 0 7 4 0 0 4 6 1 6 5 0 1 4 0 6 2 1 3 4 0 8 0 5 0 4 6 2 3 7 0 1 6 0 5 1 0 0 7 0 2 4 0 11 1 4 2 6 1 0 1 0 0 2 1 0 9 8 2 8 1 0 1 7 2 1 5 2 1 3 0 10 1 0 11 1 8 1 4 9 2 4 2 0 4 10 0 3 1 0 8 5 0 4 6 0 7 5 1 0 3 1 4...
output:
0 8 8 6 8 8 10 7 8 6 8 9 7 6 6 8 4 6 7 5 6 8 7 7 6 6 3 6 8 6 8 10 8 7 10 10 8 6 11 7 8 6 8 7 8 8 6 11 8 8 8 8 7 6 8 4 6 6 5 7 5 8 7 7 11 7 6 7 6 8 8 6 6 7 6 7 8 7 7 11 7 7 7 6 9 7 8 7 7 6 6 8 8 6 8 8 5 8 8 3 7 11 7 8 8 7 11 9 8 7 11 7 7 9 8 7 11 8 4 10 9 7 6 6 8 8 7 8 9 6 7 8 5 6 6 6 5 14 8 7 7 7 7 ...
result:
points 0.80 Partially Accepted. You Got 80% score.