Submission #993844

#	Time	Username	Problem	Language	Result	Execution time	Memory
993844		simona1230	Wells (CEOI21_wells)	C++17	0 / 100	7 ms	43868 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;
    }

    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 dfs(int i,int p,int h1,int h2)// h1 ot kolko vyrha nqma h2 na kolko vyrha e naj blizkoto
{
    if(mark[i])
    {
        if(h2>=k)return 0;
        h1=0,h2=1;
    }
    else
    {
        if(h1>=k)return 0;
        h1++;
        if(h2!=-1)h2++;
    }

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

        if(!dfs(nb,i,h1,h2))return 0;
    }
    return 1;
}

bool check()
{
    for(int i=1;i<=n;i++)
    {
        if(!dfs(i,0,1,-1))return 0;
    }
    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())
            {
                //cout<<i<<endl;
                ways++;
                for(int j=1;j<=n;j++)
                    if(mark[j])used[j]=1;
            }
        }
    }

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


    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:75:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int j=0; j<v[i].size(); j++)
      |                  ~^~~~~~~~~~~~
wells.cpp: In function 'bool dfs(int, int, int, int)':
wells.cpp:100:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     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