Submission #1230818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230818		Matthewwww	Burza (COCI16_burza)	C++17	64 / 160	990 ms	476 KiB

burza

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

double chance = 0.01, multi = 0.9999;

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> 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;
		int f = mt()%k;
		alive[atd[f][ptr[f]]] = 1;
		int b = ptr[f];
		ptr[f] = mt()%atd[f].size();
		alive[atd[f][ptr[f]]] = 0;
		int nw = dfs(0, 0, k, 0, adj, alive);
		if (nw <= sc || chance*(double)sc/(double)nw < (double)mt()/(double)(int)mt.max) {
			sc = nw;
			continue;
		}
		alive[atd[f][ptr[f]]] = 1;
		ptr[f] = b;
		alive[atd[f][b]] = 0;
	}
	cout << "NE\n";
}

• Subtask 1: 16 / 16
• Subtask 2: 0 / 16
• Subtask 3: 16 / 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