Submission #1190521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190521		KaleemRazaSyed	Wells (CEOI21_wells)	C++20	0 / 100	20 ms	35656 KiB

wells

#include<bits/stdc++.h>

using namespace std;

const int N = 1.5e6 + 10, mod = 1e9+7;
int n, k;
vector<int> G[N];
bool done[N], mark[N];

int dfs(int v, int p = -1)
{
  int ans = 0;
  for(int u : G[v])
    if(u != p)
      ans = max(ans, 1 + dfs(u, v));
  return ans;
}

int diameter()
{
  int ans = 0;
  for(int v = 1; v <= n; v ++)
    ans = max(ans, dfs(v));
  return ans;
}

bool Close;

void Dfs(int v, int p = -1, int d = 1)
{
  if(Close || d >= k) return;
  
  for(int u : G[v])
      if(u != p)
	{
	  if(mark[u] && d + 1 <= k)
	    {
	      // cerr << u << ' ' << d + 1 << endl;
	      Close = true;
	    }
	  Dfs(u, v, d + 1);
	}      
}


bool check(int v)
{
  bool seen[n + 1] = {};

  seen[v] = 1;
  
  vector<int> level = {v};
  int l = 0;

  vector<int> vec;
  
  Close = false;  

  while(level.size())
    {
      if(l == 1)
	for(int v : level)
	  vec.push_back(v);
      
      vector<int> nl;
      for(int v : level)
	{
	  int cnt = 0;
	  for(int u : G[v])
	    if(!seen[u])
	      cnt++, seen[u] = 1, nl.push_back(u);

	  if(l == k - 1 && cnt > 1)
	    Close = true;
	    
	}
      l = l % k + 1;
     
      level = nl;
    }
  
  for(int v : vec)
    done[v] = mark[v] = true;

  for(int i = 0; i < vec.size(); i ++)
    Dfs(vec[i]);

  for(int v : vec)
    mark[v] = false;
  
  return !Close;
}

int main()
{
  cin >> n >> k;

  if(k == 2)
    {
      cout << "YES\n";
      cout << 2 << endl;
      return 0;
    }
  
  for(int i = 1; i < n; i ++)
    {
      int a, b;
      cin >> a >> b;
      G[a].push_back(b);
      G[b].push_back(a);
    }

  int x = diameter();

  if(x + 1 < k)
    {
      cout << "YES\n";
      int ans = 1;
      for(int i = 0; i < n; i ++)
	ans = (ans * 2) % mod;
      cout << ans << endl;
      return 0;
    }

  int ans = 0;
  for(int v = 1; v <= n; v++)
    if(!done[v])
      ans += check(v);
  
  cout << (ans == 0 ? "NO" : "YES") << endl;
  cout << ans << endl;
  
  return 0;
}

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