Submission #744024

#	Time	Username	Problem	Language	Result	Execution time	Memory
744024		hmm789	Wells (CEOI21_wells)	C++14	0 / 100	22 ms	35592 KiB

wells

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
#define INF 1000000000000000000

vector<int> adj[1500000], v0;
int clr[1500000], depth[1500000], n, k, mx;
bool ok, used[1500000];

int dfs(int x, int p, int c) {
	clr[x] = c;
	if(c == 0) v0.push_back(x);
	depth[x] = 0;
	for(int i : adj[x]) if(i != p) {
		depth[x] = max(depth[x], dfs(i, x, (c+1)%k)+1);
	}
	return depth[x];
}

pair<int, int> dfs2(int x, int p) {
	pair<int, int> ans = {INF, -INF};
	vector<int> v, v2, v3;
	for(int i : adj[x]) if(i != p) {
		pair<int, int> tmp = dfs2(i, x);
		if(tmp.second == -INF) {
			v2.push_back(depth[i]);
		} else {
			ans.first = min(ans.first, tmp.first+1);
			ans.second = max(ans.second, tmp.second+1);
			v.push_back(tmp.first);
			v3.push_back(tmp.second);
		}
	}
	if(clr[x]) {
		sort(v3.rbegin(), v3.rend());
		if(v3.size() > 1 && v3[0]+v3[1]+1 >= k) ok = false;
		sort(v.begin(), v.end());
		if(v.size() > 1 && v[0]+v[1]+3 <= k) ok = false;
		sort(v2.rbegin(), v2.rend());
		if(v2.size() > 1 && v2[0]+v2[1]+3 >= k) ok = false;
		if(v2.size() && v3.size() && v2[0]+v3[0]+2 >= k) ok = false;
	}
	if(clr[x] == 0) return {0, 0};
	else return ans;
}

int dfs3(int x, int p) {
	int ans = 1;
	vector<int> v;
	for(int i : adj[x]) if(i != p) {
		int tmp = dfs3(i, x);
		v.push_back(tmp);
		ans = max(ans, tmp+1);
	}
	if(p == -1) {
		sort(v.rbegin(), v.rend());
		if(v.size() > 0) mx = max(mx, v[0]+1);
		if(v.size() > 1) mx = max(mx, v[0]+v[1]+1);
	}
	return ans;
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int x, y, ans = 0, mult = 1;
	cin >> n >> k;
	for(int i = 0; i < n-1; i++) {
		cin >> x >> y;
		x--; y--;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	for(int i = 0; i < n; i++) {
		if(used[i]) continue;
		mx = 0;
		dfs3(i, -1);
		if(mx < k) {
			mult = (2*mult)%MOD;
			continue;
		}
		v0.clear();
		dfs(i, -1, 0);
		ok = true;
		dfs2(i, -1);
		if(ok) {
			ans++;
			for(int j : v0) used[j] = true;
		}
	}
	if(ans == 0) cout << "NO\n";
	else cout << "YES\n";
	cout << (ans*mult)%MOD << '\n';
}

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