QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#783161 | #9630. 沙堆 | wcdr | ML | 18ms | 62680kb | C++17 | 5.7kb | 2024-11-26 00:13:36 | 2024-11-26 00:13:39 |
Judging History
answer
#include<random>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstdio>
#include<cstdlib>
#include<climits>
//#define NDEBUG
#include<cassert>
#include<cstring>
#include<complex>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<bitset>
//#define LL __int128
#define LL long long
#define ULL unsigned LL
#define uint unsigned int
//#define int LL
//#define double long double
#define mkp make_pair
#define par pair<int,int>
#define psb push_back
#define epb emplace_back
#define f(x) ((x).first)
#define s(x) ((x).second)
using namespace std;
#define Lbt(x) ((x)&(-(x)))
#define Swap(x,y) (x^=y^=x^=y)
const int Mxxx=1e5;
inline char gc()
{
// return getchar();
static char buf[Mxxx],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxxx,stdin),p1==p2)?EOF:*p1++;
}
inline char pc(char ch,bool fl=false)
{
// return fl?0:putchar(ch),0;
static char buf[Mxxx],*p1=buf,*p2=buf+Mxxx;
return (fl||((*p1++=ch)&&p1==p2))&&(fwrite(buf,1,p1-buf,stdout),p1=buf),0;
}
#define output pc('!',true)
inline int read()
{
char ch=gc();
int gans=0,gflag=0;
for(;ch<'0'||'9'<ch;gflag|=ch=='-',ch=gc());
for(;'0'<=ch&&ch<='9';gans=(gans<<1)+(gans<<3)+(ch^48),ch=gc());
return gflag?-gans:gans;
}
template<typename T>
inline char read(T&gans)
{
char ch=gc();
int gflag=0;gans=0;
for(;ch<'0'||'9'<ch;gflag|=ch=='-',ch=gc());
for(;'0'<=ch&&ch<='9';gans=(gans<<1)+(gans<<3)+(ch^48),ch=gc());
return gans=gflag?-gans:gans,ch;
}
template<typename T>
inline void write(T x)
{
if(x>9)write(x/10);
pc(x%10^48);
}
template<typename T>
inline void writenum(T x,char ch)
{
if(x<0)pc('-'),x=-x;
write(x);pc(ch);
}
inline void writechar(char x,char ch)
{
pc(x);pc(ch);
}
template<typename T>
inline T Max(T x,T y)
{
return x>y?x:y;
}
template<typename T>
inline T Min(T x,T y)
{
return x<y?x:y;
}
template<typename T>
inline T Abs(T x)
{
return x<0?-x:x;
}
template<typename T>
inline void ckmx(T&x,T y)
{
x=Max(x,y);
}
template<typename T>
inline void ckmn(T&x,T y)
{
x=Min(x,y);
}
const int Mx=1e6;
int n,cnt,c[Mx+5],h[Mx+5],du[Mx+5],nxt[(Mx<<1)+5],tto[(Mx<<1)+5];
inline void ade(int x,int y){nxt[++cnt]=h[x];tto[h[x]=cnt]=y;du[y]++;}
inline void Ade(int x,int y){ade(x,y),ade(y,x);}
inline vector<int> Mrg(vector<int>&x,vector<int>&y)
{
int sx=!x.empty()?x.size():0,sy=!y.empty()?y.size():0;
int i,j;vector<int>v;v.clear();
for(i=j=0;i<sx&&j<sy;)v.epb((x[i]<=y[j]?x[i++]:y[j++]));
for(;i<sx;i++)v.epb(x[i]);
for(;j<sy;j++)v.epb(y[j]);
return v;
}
vector<int>vec[Mx+5],rcd[Mx+5];int tt[Mx+5];
inline void DFS(int x,int y)
{
int i,j,k,t,p,v,ls,to;vector<int>tmp;tmp.clear();
for(i=h[x];i;i=nxt[i])
{
if((to=tto[i])^y)
{
DFS(to,x);
tmp=Mrg(tmp,vec[to]);
}
}
// cout<<"Ck_tmp_before:"<<x<<" "<<(!tmp.empty()?tmp.size():0)<<":";
// for(int vv:tmp)cout<<vv<<" ";
// cout<<"\n";
// for(i=1,j=0,k=!tmp.empty()?tmp.back():0;c[x]>=du[x]&&i<=k;i++)
// {
// for(t=0;j<(int)tmp.size()&&tmp[j]==i;j++)t++;
// c[x]-=t+(y!=0);if(y)c[y]++;
// tt[x]++;
// }
for(ls=i=0,k=!tmp.empty()?tmp.size():0;i<k&&c[x]>=du[x];i=j)
{
for(j=i;j<k&&tmp[j]==tmp[i];j++);
t=j-i;t+=(y?tmp[i]-ls:0);
// if(c[x]-t<du[x]&&(tmp[i]>ls+1)&&y&&c[x]-(tmp[i]-ls-1)<du[x])
if(tmp[i]>ls+1&&y&&c[x]-(tmp[i]-ls-1)<du[x])
{
t=c[x]-du[x]+1;c[x]-=t;
tt[x]+=t;c[y]+=t;
break;
}
c[x]-=t;tt[x]+=tmp[i]-ls;
if(y)c[y]+=tmp[i]-ls;
ls=tmp[i];
}
// if(i<=k)
if(i<k)
{
assert(c[x]<du[x]);
vector<int>v;v.clear();
// for(;j<(int)tmp.size();j++)v.epb(tmp[j]-tt[x]);
for(;i<k;i++)v.epb(tmp[i]-tt[x]);
swap(v,tmp);
}
else
{
tmp.clear();
if(c[x]>=du[x])
{
assert(y);
t=c[x]-du[x]+1;//tt[x]+=t;
c[x]-=t;c[y]+=t;
}
}
// cout<<"Ck_tmp_after:"<<x<<" "<<(!tmp.empty()?tmp.size():0)<<":";
// for(int vv:tmp)cout<<vv<<" ";
// cout<<"\n";
for(i=1;i<=du[x]-1-c[x];i++)vec[x].epb(i);
for(i=0,ls=0,p=du[x]-1-c[x],k=!tmp.empty()?tmp.size():0;i<k;i++)
{
vec[x].epb(p+(v=tmp[i])-ls+1);
rcd[x].epb(ls=v);p=vec[x].back();
}
// cout<<"Ck_vec:"<<x<<" "<<(!vec[x].empty()?vec[x].size():0)<<":";
// for(int vv:vec[x])cout<<vv<<" ";
// cout<<"\n";
// cout<<"Ck_Final_c:"<<x<<":"<<c[x]<<" "<<du[x]<<"|"<<tt[x]<<" "<<c[y]<<"\n";
}
inline void Slv(int x,int y)
{
int i,j,k,t,to;int ls;
// for(i=1,j=0,k=!rcd[x].empty()?rcd[x].back():0;c[x]>=du[x]&&i<=k;i++)
// {
// for(t=0;j<(int)rcd[x].size()&&rcd[x][j]==i;j++)t++;
// c[x]-=t+(y!=0);tt[x]++;
// }
for(ls=i=0,k=!rcd[x].empty()?rcd[x].size():0;i<k&&c[x]>=du[x];i=j)
{
for(j=i;j<k&&rcd[x][j]==rcd[x][i];j++);
t=j-i;t+=(y?rcd[x][i]-ls:0);
// if(c[x]-t<du[x]&&(rcd[x][i]>ls+1)&&y&&c[x]-(rcd[x][i]-ls-1)<du[x])
if(rcd[x][i]>ls+1&&y&&c[x]-(rcd[x][i]-ls-1)<du[x])
{
t=c[x]-du[x]+1;c[x]-=t;
tt[x]+=t;
break;
}
c[x]-=t;tt[x]+=rcd[x][i]-ls;
ls=rcd[x][i];
}
// cout<<"Slv???:"<<x<<" "<<k<<":"<<c[x]<<" "<<du[x]<<"???"<<i<<"\n";
if(c[x]>=du[x])
{
assert(i==k);
t=c[x]-du[x]+1;//tt[x]+=t;
c[x]-=t;
}
for(i=h[x];i;i=nxt[i])
{
if((to=tto[i])^y)
{
c[to]+=tt[x];
Slv(to,x);
}
}
}
signed main()
{
#ifndef ONLINE_JUDGE
// freopen("_.in","r",stdin);
// freopen("_.out","w",stdout);
#endif
int i,s=0;n=read();
for(i=1;i<n;i++)Ade(read(),read());
for(i=1;i<=n;i++)c[i]=read(),s+=du[i]-1;
for(i=1;i<=n;i++)if((s-=c[i])<0)return writenum(-1,10),output;
DFS(1,0);Slv(1,0);for(i=1;i<=n;i++)writenum(c[i],i==n?10:32);
return output;
}
/*
6
1 2
2 3
2 4
1 5
4 6
1 1 0 0 1 1
*/
/*
12
1 2
1 3
2 4
3 5
5 6
2 7
7 8
4 9
8 10
5 11
3 12
2 0 0 0 1 0 1 0 1 1 0 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 58740kb
input:
6 1 2 2 3 2 4 1 5 4 6 1 1 0 0 1 1
output:
1 2 0 1 0 0
result:
ok single line: '1 2 0 1 0 0'
Test #2:
score: 0
Accepted
time: 8ms
memory: 58916kb
input:
12 1 2 1 3 2 4 3 5 5 6 2 7 7 8 4 9 8 10 5 11 3 12 2 0 0 0 1 0 1 0 1 1 0 1
output:
0 1 2 1 1 0 1 1 0 0 0 0
result:
ok single line: '0 1 2 1 1 0 1 1 0 0 0 0'
Test #3:
score: 0
Accepted
time: 8ms
memory: 58912kb
input:
40 1 2 2 3 1 4 3 5 5 6 6 7 4 8 6 9 8 10 6 11 6 12 9 13 10 14 7 15 9 16 15 17 15 18 12 19 18 20 16 21 18 22 22 23 5 24 22 25 2 26 24 27 14 28 27 29 20 30 29 31 30 32 20 33 26 34 26 35 19 36 11 37 34 38 37 39 29 40 3 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0 0 1 1 3 0 1 0 3 0 0 0 1 0 0 0 0 0 0 0 0 0 2 1
output:
1 1 0 1 0 4 1 0 2 0 1 0 0 0 0 1 0 2 1 1 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0
result:
ok single line: '1 1 0 1 0 4 1 0 2 0 1 0 0 0 0 ...0 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0'
Test #4:
score: 0
Accepted
time: 14ms
memory: 61588kb
input:
5000 1 2 1 3 2 4 4 5 3 6 5 7 7 8 6 9 8 10 9 11 10 12 11 13 13 14 14 15 12 16 16 17 15 18 17 19 16 20 18 21 16 22 15 23 20 24 24 25 25 26 22 27 23 28 19 29 27 30 29 31 27 32 28 33 32 34 31 35 26 36 34 37 35 38 35 39 33 40 38 41 40 42 42 43 30 44 41 45 37 46 39 47 47 48 36 49 48 50 46 51 44 52 51 53 4...
output:
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 2 ...
result:
ok single line: '1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'
Test #5:
score: 0
Accepted
time: 8ms
memory: 62464kb
input:
5000 1 2 1 3 2 4 3 5 4 6 5 7 6 8 8 9 7 10 9 11 10 12 6 13 11 14 12 15 13 16 16 17 14 18 17 19 17 20 19 21 15 22 21 23 22 24 18 25 23 26 24 27 25 28 28 29 27 30 29 31 26 32 30 33 19 34 34 35 32 36 20 37 37 38 31 39 35 40 39 41 40 42 42 43 41 44 33 45 43 46 38 47 46 48 45 49 48 50 44 51 49 52 51 53 50...
output:
1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 ...
result:
ok single line: '1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'
Test #6:
score: 0
Accepted
time: 18ms
memory: 61848kb
input:
5000 1 2 1 3 2 4 3 5 4 6 5 7 6 8 8 9 7 10 10 11 9 12 11 13 12 14 13 15 15 16 14 17 17 18 16 19 18 20 19 21 21 22 20 23 22 24 23 25 24 26 26 27 25 28 28 29 27 30 29 31 31 32 30 33 32 34 33 35 35 36 34 37 36 38 37 39 39 40 38 41 40 42 31 43 41 44 43 45 44 46 42 47 46 48 45 49 48 50 49 51 51 52 52 53 5...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 2 0 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 2 1 1 1 1 2 1 2 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 ...
result:
ok single line: '1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'
Test #7:
score: 0
Accepted
time: 11ms
memory: 61556kb
input:
5000 1 2 1 3 2 4 3 5 5 6 4 7 7 8 6 9 9 10 10 11 8 12 11 13 13 14 12 15 14 16 16 17 7 18 15 19 18 20 19 21 17 22 22 23 20 24 24 25 23 26 21 27 25 28 27 29 29 30 28 31 26 32 31 33 30 34 32 35 35 36 34 37 33 38 38 39 39 40 40 41 37 42 41 43 43 44 42 45 36 46 44 47 45 48 46 49 48 50 47 51 43 52 49 53 52...
output:
1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 2 1 1 1 2 0 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 0 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 0 1 1 0 2 1 1 1 0 2 1 1 1 0 1 1 1 0 0 1 1 1 1 1 2 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 4 0 1 0 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok single line: '1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'
Test #8:
score: 0
Accepted
time: 9ms
memory: 61568kb
input:
5000 1 2 1 3 2 4 3 5 5 6 4 7 6 8 8 9 8 10 10 11 9 12 11 13 7 14 13 15 12 16 14 17 15 18 16 19 18 20 19 21 20 22 17 23 21 24 24 25 23 26 26 27 22 28 25 29 27 30 28 31 31 32 30 33 32 34 33 35 34 36 35 37 37 38 38 39 36 40 40 41 39 42 29 43 42 44 44 45 42 46 46 47 41 48 47 49 49 50 45 51 43 52 51 53 48...
output:
1 1 1 1 1 1 1 2 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 3 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 ...
result:
ok single line: '1 1 1 1 1 1 1 2 1 1 1 1 1 0 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'
Test #9:
score: 0
Accepted
time: 18ms
memory: 62680kb
input:
5000 1 2 1 3 2 4 3 5 4 6 5 7 6 8 8 9 7 10 8 11 9 12 10 13 11 14 13 15 14 16 15 17 17 18 16 19 17 20 12 21 18 22 20 23 21 24 24 25 23 26 20 27 22 28 28 29 25 30 29 31 27 32 30 33 32 34 34 35 33 36 30 37 36 38 31 39 35 40 37 41 26 42 39 43 38 44 19 45 42 46 44 47 40 48 46 49 49 50 45 51 48 52 47 53 50...
output:
1 1 0 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 1 ...
result:
ok single line: '1 1 0 1 1 1 1 2 1 1 1 1 1 1 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'
Test #10:
score: 0
Accepted
time: 15ms
memory: 61916kb
input:
5000 1 2 2 3 1 4 3 5 4 6 5 7 6 8 7 9 6 10 6 11 10 12 11 13 13 14 12 15 9 16 14 17 15 18 16 19 17 20 18 21 21 22 22 23 18 24 20 25 23 26 25 27 8 28 28 29 26 30 24 31 27 32 19 33 30 34 29 35 33 36 34 37 37 38 35 39 34 40 32 41 36 42 42 43 39 44 43 45 44 46 45 47 46 48 41 49 47 50 49 51 48 52 52 53 50 ...
output:
1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 0 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 1 0 1 1 1 3 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 4 1 1 1 2 ...
result:
ok single line: '1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'
Test #11:
score: 0
Accepted
time: 11ms
memory: 59848kb
input:
5000 1 2 2 3 3 4 4 5 1 6 6 7 7 8 5 9 8 10 10 11 9 12 12 13 11 14 13 15 10 16 15 17 14 18 17 19 17 20 16 21 20 22 19 23 22 24 23 25 24 26 25 27 25 28 21 29 18 30 26 31 27 32 30 33 31 34 32 35 34 36 36 37 37 38 38 39 35 40 39 41 40 42 29 43 41 44 44 45 42 46 41 47 43 48 28 49 47 50 46 51 50 52 51 53 5...
output:
1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 0 1 2 1 2 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 ...
result:
ok single line: '1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'
Test #12:
score: 0
Accepted
time: 13ms
memory: 61696kb
input:
5000 1 2 1 3 3 4 2 5 4 6 6 7 5 8 7 9 8 10 9 11 10 12 3 13 11 14 14 15 11 16 13 17 17 18 16 19 15 20 20 21 21 22 18 23 19 24 22 25 12 26 24 27 27 28 25 29 26 30 29 31 30 32 23 33 30 34 34 35 33 36 35 37 32 38 37 39 36 40 18 41 39 42 28 43 41 44 31 45 43 46 44 47 40 48 46 49 47 50 49 51 42 52 38 53 45...
output:
1 1 2 1 1 1 1 1 1 1 2 1 1 1 0 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 2 0 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok single line: '1 1 2 1 1 1 1 1 1 1 2 1 1 1 0 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'
Test #13:
score: -100
Memory Limit Exceeded
input:
1000000 1 2 1 3 2 4 3 5 4 6 5 7 7 8 8 9 9 10 8 11 6 12 12 13 13 14 11 15 15 16 14 17 16 18 11 19 15 20 18 21 10 22 22 23 19 24 20 25 15 26 25 27 25 28 28 29 17 30 30 31 29 32 30 33 24 34 31 35 34 36 33 37 23 38 28 39 32 40 26 41 21 42 42 43 27 44 39 45 36 46 43 47 37 48 34 49 44 50 47 51 50 52 48 53...
output:
1 1 1 1 1 1 1 2 1 1 2 1 1 1 3 1 1 1 1 1 1 1 1 1 2 1 1 3 1 2 2 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 0 1 1 1 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 2 1 1 1 1 1 1 0 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 0 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 ...