Submission #993621

#	Time	Username	Problem	Language	Result	Execution time	Memory
993621		simona1230	Wells (CEOI21_wells)	C++17	0 / 100	15 ms	35848 KiB

wells

#include <bits/stdc++.h>

using namespace std;
const int maxn=1500005;
const int mod=1e9+7;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n,k;
vector<int> v[maxn];
void read()
{
    cin>>n>>k;
    for(int i=1; i<n; i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}

int l[maxn];
int in[maxn];
void l_(int i,int p)
{
    l[i]=1;
    int m1=0,m2=0;
    for(int j=0; j<v[i].size(); j++)
    {
        int nb=v[i][j];
        if(nb==p)continue;

        l_(nb,i);
        if(m1<=l[nb])
        {
            m2=m1;
            m1=l[nb];
        }
        else m2=max(m2,l[nb]);
        l[i]=max(l[i],l[nb]+1);
    }

    //cout<<i<<" "<<l[i]<<endl;
    if(l[i]>=k||m1+m2+1>=k)
        in[i]=1;
}


void fix_(int i,int p)
{
    for(int j=0; j<v[i].size(); j++)
    {
        int nb=v[i][j];
        if(nb==p)continue;

        in[nb]=max(in[nb],in[i]);
        fix_(nb,i);
    }
}

int used[maxn];
int mark[maxn];

void mark_(int i,int x,int p)
{
    if(x==0)
    {
        mark[i]=1;
        used[i]=1;
    }

    for(int j=0; j<v[i].size(); j++)
    {
        int nb=v[i][j];
        if(nb==p)continue;

        mark_(nb,(x+1)%k,i);
    }
}

int cl[maxn],fu[maxn];
bool check(int i,int p)
{
    cl[i]=-1,fu[i]=1;
    int cl1=-1,cl2=-1;
    int fu1=0,fu2=0;

    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(nb==p)continue;

        if(!check(nb,i))
            return 0;

        if(cl[nb]!=-1)
        {
            if(cl[i]==-1)cl[i]=cl[nb]+1;
            cl[i]=min(cl[i],cl[nb]+1);

            if(cl1==-1)cl1=cl[nb];
            else if(cl1>cl[nb])cl1=cl[nb],cl2=cl1;
            else if(cl2==-1||cl2>cl[nb])cl2=cl[nb];
        }

        fu[i]=max(fu[i],fu[nb]+1);

        if(fu1<fu[nb])
        {
            fu2=fu1;
            fu1=fu[nb];
        }
        else fu2=max(fu2,fu[nb]);
    }

    if(v[i].size()==1)fu[i]=1,cl[i]=-1;
    if(mark[i])fu[i]=0,cl[i]=1;

    //cout<<i<<" "<<cl[i]<<" "<<fu[i]<<" "<<cl1<<" "<<cl2<<" "<<fu1<<" "<<fu2<<endl;

    if(mark[i])
    {
        if(cl1!=-1&&cl1<k)return 0;
        return 1;
    }


    if(cl1!=-1&&cl2!=-1&&cl1+cl2+1<=k)return 0;
    if(fu1+fu2+1>=k)return 0;
    //cout<<i<<" "<<fu[i]<<" "<<cl[i]<<endl;
    return 1;
}

void solve()
{
    int ways=0;
    for(int i=1; i<=n; i++)
    {
        if(!used[i])
        {
            //cout<<i<<": "<<endl;
            for(int j=1; j<=n; j++)
                mark[j]=cl[j]=0;
            mark_(i,0,0);
            /*for(int j=1;j<=n;j++)
                    cout<<mark[j]<<" ";
                cout<<endl;*/
            if(check(i,0))
            {
                //cout<<i<<endl;

                ways++;
            }
        }
    }

    int cnt=0;
    for(int i=1;i<=n;i++)
        if(!in[i])cnt++;

    for(int i=1;i<=cnt;i++)
    {
        ways*=2;
        ways%=mod;
    }

    if(ways)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    cout<<ways<<endl;
}

int main()
{
    speed();
    read();
    l_(1,0);
    fix_(1,0);

    solve();
    return 0;
}

Compilation message (stderr)

wells.cpp: In function 'void l_(int, int)':
wells.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int j=0; j<v[i].size(); j++)
      |                  ~^~~~~~~~~~~~
wells.cpp: In function 'void fix_(int, int)':
wells.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int j=0; j<v[i].size(); j++)
      |                  ~^~~~~~~~~~~~
wells.cpp: In function 'void mark_(int, int, int)':
wells.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int j=0; j<v[i].size(); j++)
      |                  ~^~~~~~~~~~~~
wells.cpp: In function 'bool check(int, int)':
wells.cpp:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 30