Submission #823274

#	Time	Username	Problem	Language	Result	Execution time	Memory
823274		khshg	Wells (CEOI21_wells)	C++14	0 / 100	1 ms	212 KiB

wells

#include<bits/stdc++.h>
using namespace std;
#define pb push_back

const int maxn = 200; // SUBTASK !
int N, K;
vector<int> adj[maxn], sz;
vector<bool> color, vis;

void dfs(int s, int dis) {
	vis[s] = 1;
	color[s] = (dis == K);
	for(auto& u : adj[s]) {
		if(!vis[u]) {
			dfs(u, (dis == K ? 0 : dis) + 1);
		}
	}
}

void Csz(int s, int p = -1) {
	sz[s] = 1;
	for(auto& u : adj[s]) {
		if(vis[s] || u == p) continue;
		Csz(u, s);
		sz[s] += sz[u];
	}
}

int cent(int s, int G, int p = -1) {
	for(auto& u : adj[s]) if(!vis[u] && u != p && sz[u] > G / 2) return cent(u, G, s);
	return s;
}

bool cd(int s) {
	Csz(s);
	s = cent(s, sz[s]);
	vis[s] = 1;
	bool res = 1;
	{
		multiset<int> k;
		if(color[s]) k.insert(0);
		for(auto& u : adj[s]) {
			if(vis[u]) continue;
			queue<array<int, 3>> q;
			q.push({u, s, 1});
			while(!q.empty()) {
				array<int, 3> cur = q.front();
				if(color[cur[0]]) {
					k.insert(cur[2]);
					if((int)k.size() > 2) k.erase(prev(end(k)));
					break;
				}
				q.pop();
				for(auto& c : adj[cur[0]]) {
					if(c == cur[1] || vis[c]) continue;
					q.push({c, cur[0], cur[2] + 1});
				}
			}
		}
		if((int)k.size() == 2) {
			int sum = 0; for(auto u : k) sum += u;
			res &= (K <= sum);
		}
	}
	if(!color[s]) {
		multiset<int> k;
		for(auto& u : adj[s]) {
			if(vis[u]) continue;
			queue<array<int, 3>> q;
			q.push({u, s, 1});
			while(!q.empty()) {
				array<int, 3> cur = q.front();
				q.pop();
				if(color[cur[0]]) {
					continue;
				}
				k.insert(cur[2]);
				if((int)k.size() > 2) k.erase(begin(k));
				for(auto& c : adj[cur[0]]) {
					if(c == cur[1] || vis[c]) continue;
					q.push({c, cur[0], cur[2] + 1});
				}
			}
		}
		if((int)k.size()) {
			int sum = 0; for(auto& u : k) sum += u;
			res &= (sum + 1 < K);
		}
	}
	for(auto& u : adj[s]) if(!vis[u]) res &= cd(u);
	return res;
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> N >> K;
	for(int i = 1, u, v; i < N; ++i) {
		cin >> u >> v;
		--u; --v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	for(int i = 0; i < N; ++i) {
		vis = color = vector<bool>(N, false);
		dfs(i, K);
		vis = vector<bool>(N, false);
		sz = vector<int>(N, 0);
		if(cd(0)) {
			cout << "YES\n";
			return 0;
		}
	}
	cout << "NO\n";
	return 0;
}

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