#28 #39 TLE 爆搜求调
查看原帖
#28 #39 TLE 爆搜求调
848964
hzoi_Shadow楼主2023/8/5 18:43
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define sort stable_sort 
#define endl '\n'
struct node
{
	ll to,next;
}e[20000001];
ll head[20000001],dep[20000001],summ[20000001],cnt=0,num=0;
bool vis[20000001],dis[20000001],f[20000001];
inline ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-')
        {
            f=-1;
        }
        c=getchar();
    }
    while('0'<=c&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
void write(ll x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar((x%10)+'0');
}
inline void add(ll u,ll v)
{
    cnt++;
    e[cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
void dfs(ll x,ll fa)
{
	ll i;
	dep[x]=dep[fa]+1;
    for(i=head[x];i;i=e[i].next)
    {
        if(e[i].to!=fa)
        {
            dfs(e[i].to,x);
        }
    }
}
void search(ll x,ll sum,ll n)
{	
	if(num+dep[x]>sum)
	{
		return;
	}
	if(num+dep[x]==sum)
	{
		vis[x]=true;
		for(ll i=1;i<=n;i++)
		{
			if(!vis[i])
			{
				printf("0 ");
			}
			else
			{
				printf("1 ");
			}
		}
		exit(0);
	}
	if(num+dep[x]<sum)
	{
		num+=dep[x];
		vis[x]=true;
		for(ll i=x+1;i<=(n+1)/2;i++)
		{
			if(!vis[i])
			{
				search(i,sum,n);
			}
		}
		for(ll i=(n+1)/2+1;i<=n;i++)
		{
			if(!vis[i])
			{
				search(i,sum,n);
			}
		}
	}
}
int main()
{
    ll n,i,j,u,v,sum=0;
    n=read();
    for(i=1;i<n;i++)
	{
		u=read();
		v=read();
        if(u==1)
        {
        	f[v]=true;
        	add(u,v);
		}
		else
		{
			if(v==1)
			{
				f[u]=true;
				add(v,u);
			}
			else
			{
				if(f[u]==true)
				{
					add(u,v);
				}
				else
				{
					if(f[v]==true)
					{
						add(v,u);
					}
					else
					{
						add(u,v);
						add(v,u);
					}
				}
			}
		}
    }
    dfs(1,0);
    for(i=1;i<=n;i++)
    {
        sum+=dep[i];
        summ[i]=summ[i-1]+dep[i];
    }
    if(sum%2==0)
    {
    	sum>>=1;
		for(i=1;i<=n&&summ[n]-summ[i-1]>=sum;i++)
		{
			if(!dis[dep[i]])
			{
				num=0;
				for(j=1;j<=n;j++)
				{
					vis[j]=false;
				}
				search(i,sum,n);
				dis[dep[i]]=true;
			}
		}
		printf("-1");
	}
	else
	{
		printf("-1");
	}
    return 0;
}
2023/8/5 18:43
加载中...