제출 #1230855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1230855		Matthewwww	Burza (COCI16_burza)	C++17	48 / 160	990 ms	472 KiB

burza

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif

double chance = 0.1, multi = 0.9999;
int mxu = 1;

int fdep (int i, int f, vector<vector<int>> &adj, vector<int> &dep) {
	int mx = dep[i];
	for (int j: adj[i]) {
		if (j == f) continue;
		dep[j] = dep[i]+1;
		mx = max(mx, fdep(j, i, adj, dep));
	}
	return mx;
}

int dfs (int i, int f, int k, int d, vector<vector<int>> &adj, vector<bool> &alive) {
	if (!alive[i]) return 0;
	if (d >= k) return 1;
	int ans = 0;
	for (int j: adj[i]) if (j != f) ans += dfs(j, i, k, d+1, adj, alive);
	return ans;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, k;
	cin >> n >> k;
	vector<vector<int>> adj(n);
	for (int a, b, i = 1; i < n; i++) {
		cin >> a >> b;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
	}
	vector<int> dep(n, 0);
	int md = fdep(0, 0, adj, dep);
	k = min(k, md);
	vector<vector<int>> atd(k);
	for (int i = 0; i < n; i++) if (dep[i] && dep[i] <= k) atd[dep[i]-1].push_back(i);
	vector<int> rng;
	for (int i = 0; i < k; i++) for (int j: atd[i]) rng.push_back(i);
	vector<int> ptr(k, 0);
	vector<bool> alive(n, 1);
	for (int i = 0; i < k; i++) alive[atd[i][0]] = 0;
	int sc = dfs(0, 0, k, 0, adj, alive);
	mt19937 mt(time(NULL));
	for (auto t = chrono::steady_clock::now(); chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now()-t).count() < 990; chance *= multi) {
		if (!sc) return cout << "DA\n", 0;
		vector<pair<int, int>> mv;
		for (int eui = 1; eui <= mxu; eui++) {
			if (eui == mxu || mt()%2) {
				for (int aoe = 0; aoe < eui; aoe++) {
					int f = rng[mt()%rng.size()];
					alive[atd[f][ptr[f]]] = 1;
					int b = ptr[f];
					ptr[f] = mt()%atd[f].size();
					alive[atd[f][ptr[f]]] = 0;
					mv.push_back({f, b});
				}
				break;
			}
		}
		int nw = dfs(0, 0, k, 0, adj, alive);
		if (nw <= sc || chance*(double)sc/(double)nw < (double)mt()/(double)(long long)mt.max) {
			sc = nw;
			continue;
		}
		while (mv.size()) {
			int f = mv.back().f, b = mv.back().s;
			mv.pop_back();
			alive[atd[f][ptr[f]]] = 1;
			ptr[f] = b;
			alive[atd[f][b]] = 0;
		}
	}
	cout << "NE\n";
	err << chance << "\n";
}

• Subtask 1: 16 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 16 / 16
• Subtask 7: 0 / 16
• Subtask 8: 16 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16