Hi guys , I just solved the fourth problem of round 381 , Hope you like it , feel free to comment any better solution .
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<vector>
#define N 310
#define pb push_back
using namespace std;
struct node{int p,c,id;};
vector<node> A[N],B[N],C[N],D;
int n,mx[N],f[N][N],need[N],can[N][N],has[N],a[N],num,ans[N];
bool v[N],b[N];
int read()
{
int t=0;char c=getchar();
while(c!=’?#8217; && (c<‘0′ || c>’9′)) c=getchar();
if(c==’?#8217;) return -1;
while(c>=’0′ && c<=’9′) {t=t*10+c-‘0’;c=getchar();}
return t;
}
void print()
{
for(int i=1;i<=n;i++) printf(“%d “,ans[i]);
}
int solve(int o)
{
for(int i=1;i<=n;i++) ans[i]=0;
int cnt=0,siz;
for(int i=1;i<=n;i++)
for(int j=0;j<=mx[i];j++)
f[i][j]=0;
for(int i=1;i<=n;i++)
{
if(v[i]==0) continue;
int cir=0;
siz=A[i].size();
for(int j=0;j<siz;j++)
{
int p=A[i][j].p;
if(f[i][p]==0) f[i][p]=A[i][j].id;
if(p==0) cir++;
}
if(cir==0) need[i]=i;
else if(cir%i==0) need[i]=0;
else need[i]=i-cir%i;
can[i][0]=min(need[i],(int)(C[0].size()));
for(int j=1;j<=mx[i];j++) if(f[i][j]==0) need[i]++;
for(int j=1;j<=mx[i];j++)
{
can[i][j]=can[i][j-1];
if(f[i][j]==0 && C[j].size()) can[i][j]++;
}
}
for(int i=1;i<=n;i++) has[i]=B[i].size();
for(int i=1;i<=n;i++) b[i]=0;
for(int i=n;i>=1;i–)
{
siz=C[i].size();int now=0;
for(int j=1;j<=n;j++)
{
if(v[j]==0 || mx[j]<i || f[j][i]) continue;
if(now==siz) break;
if(has[j]>=need[j]) continue;
if(has[j]+can[j][i]<=need[j]) {f[j][i]=C[i][now].id;now++;need[j]–;}
}
for(int j=1;j<=n;j++)
{
if(v[j]==0 || mx[j]<i || f[j][i]) continue;
if(now==siz) break;
if(has[j]>=need[j]) continue;
f[j][i]=C[i][now].id;now++;
need[j]–;
}
for(int j=1;j<=n;j++)
{
if(v[j]==0 || mx[j]<i || f[j][i]) continue;
if(has[j]>0) {int k=B[j].size()-has[j];f[j][i]=B[j][k].id;has[j]–;}
else if(cnt<D.size()) {f[j][i]=D[cnt].id;cnt++;}
else return 0;
need[j]–;
}
}
int now=0;
for(int i=1;i<=n;i++)
{
if(v[i]==0) continue;
siz=A[i].size();num=0;
for(int j=0;j<siz;j++) if(A[i][j].p==0) a[++num]=A[i][j].id;
while(now<C[0].size() && has[i]<need[i])
{
a[++num]=C[0][now].id;now++;
need[i]–;
}
if(has[i]+D.size()-cnt<need[i]) return 0;
while(need[i]>0 && has[i]>0)
{
int k=B[i].size()-has[i];has[i]–;
a[++num]=B[i][k].id;
need[i]–;
}
while(need[i]>0)
{
a[++num]=D[cnt].id;cnt++;
need[i]–;
}
for(int j=1;j<=num;j++)
{
if(f[i][0]==0) f[i][0]=a[j];
if(j%i) ans[a[j]]=a[j+1];
else ans[a[j]]=a[j-i+1];
}
for(int j=1;j<=mx[i];j++) ans[f[i][j]]=f[i][j-1];
siz=A[i].size();
for(int j=0;j<siz;j++)
if(ans[A[i][j].id]==0) ans[A[i][j].id]=f[i][A[i][j].p-1];
siz=B[i].size();
for(int j=0;j<siz;j++)
if(ans[B[i][j].id]==0) ans[B[i][j].id]=f[i][0];
}
for(int i=1;i<=n;i++)
{
siz=C[i].size();
for(int j=0;j<siz;j++)
if(ans[C[i][j].id]==0) ans[C[i][j].id]=f[o][i-1];
}
num=0;
siz=C[0].size();
for(int i=0;i<siz;i++) if(ans[C[0][i].id]==0) a[++num]=C[0][i].id;
siz=D.size();
for(int i=cnt;i<siz;i++) a[++num]=D[i].id;
for(int i=1;i<num;i++) ans[a[i]]=a[i+1];
ans[a[num]]=a[1];
return 1;
}
int main()
{
scanf(“%d”,&n);
int maxd=0;
bool bo=0;
for(int i=1;i<=n;i++)
{
int p,c;p=read();c=read();
maxd=max(maxd,p);
node t=(node){p,c,i};
if(c!=-1 && p!=-1) A[c].pb(t);
else if(c!=-1 && p==-1) B[c].pb(t);
else if(c==-1 && p!=-1) C[p].pb(t);
else D.pb(t);
if(c!=-1) v[c]=bo=1,mx[c]=max(mx[c],p);
}
if(bo==0) v[1]=1;
for(int i=1;i<=n;i++)
{
if(v[i]==0) continue;
int t=mx[i];
mx[i]=max(mx[i],maxd);
if(solve(i)) {print();return 0;}
mx[i]=t;
}
printf(“-1\n”);
return 0;
}
, problem: (D) Recover a functional graph Solution in C/C++. Hi guys , I just solved the fourth problem of round 381 , Hope){kind=link}