Submission #640028

#	Time	Username	Problem	Language	Result	Execution time	Memory
640028		benedict0724	Wells (CEOI21_wells)	C++17	0 / 100	1 ms	340 KiB

wells

#include <iostream>
#include <stack>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>

using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;

vector<int> adj[202];
int dist[202][202];
bool vis[202];
int chk[202], n, k;
ll pw = 1;

int getDist(int root, int x, int p)
{
    if(x == root)
    {
        int Fi = 0, Se = 0;
        for(int i : adj[x])
        {
            dist[root][i] = 1;
            Se = max(Se, getDist(root, i, x));
            if(Se > Fi) swap(Se, Fi);
        }
        if(Fi + Se + 1 < k) pw = (pw * 2)%mod;
        return 0;
    }
    int ret = dist[root][x];
    for(int i : adj[x])
    {
        if(i == p) continue;
        dist[root][i] = dist[root][x] + 1;
        ret = max(ret, getDist(root, i, x));
    }
    return ret;
}

int tmp[202];
void dfs(int x, int p, int col)
{
    for(int i : adj[x])
    {
        if(i == p) continue;
        if(chk[i] == col) continue;
        
        tmp[i] = tmp[x] + 1;
        dfs(i, x, col);
    }
}

int getRadius(int x, int col)
{
    if(chk[x] == col) return 0;
    if(vis[x]) return 0;
    for(int i=1;i<=n;i++) tmp[i] = 0;
    dfs(x, -1, col);
    
    int S = 1;
    for(int i=1;i<=n;i++) if(tmp[S] < tmp[i]) S = i;
    for(int i=1;i<=n;i++) tmp[i] = 0;
    dfs(S, -1, col);
    int ret = 0;
    for(int i=1;i<=n;i++) ret = max(ret, tmp[i]);
    return ret;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> k;
    for(int i=1;i<n;i++)
    {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        getDist(i, i, -1);
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout << dist[i][j] << " ";
        }
        cout << "\n";
    }
    
    ll ans = 0;
    for(int i=1;i<=n;i++)
    {
        if(chk[i]) continue;
        vector<int> v;
        for(int j=1;j<=n;j++) if(dist[i][j]%k == 0)
        {
            v.push_back(j);
            chk[j] = i;
        }
        bool flag = true;
        for(int a : v) for(int b : v)
            if(dist[a][b]%k != 0) flag = false;
        
        int rad = 0;
        for(int j=1;j<=n;j++) vis[j] = false;
        for(int j=1;j<=n;j++)
            rad = max(rad, getRadius(j, i));
        
        if(rad >= k - 1) flag = false;
        
        if(flag)
        {
            //cout << i << " ";
            ans++;
        }
    }
    //cout << "\n";
    
    if(ans == 0) cout << "NO\n0";
    else cout << "YES\n" << (ans * pw)%mod;
}

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