Submission #46407

#	Time	Username	Problem	Language	Result	Execution time	Memory
46407		RockyB	Mousetrap (CEOI17_mousetrap)	C++17	0 / 100	439 ms	82548 KiB

mousetrap

/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)1e6 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n, t, m;

struct solve {
	int sz[N];
	vector <int> g[N];


	void dfs(int v = m, int p = -1) {
		sz[v] = 1;
		for (auto to : g[v]) {
			if (to == p) continue;
			dfs(to, v);
			sz[v] += sz[to];
		}
	}

	int calc(int v = m, int p = t) {
		int mx = -1, cnt = 0;
		for (auto to : g[v]) {
			if (to == p) continue;
			++cnt;
			if (mx == -1 || sz[to] > sz[mx]) mx = to;
		}
		int go = -1;
		for (auto to : g[v]) {
			if (to == p || to == mx) continue;
			if (go == -1 || sz[to] > sz[go]) go = to;
		}
		int res = cnt;
		if (cnt > 1) res--;
		if (go != -1) res += min(1, calc(go, v) + 2);
		return res;
	}
	void prep() {
		memset(sz, 0, sizeof(sz));
		for (int i = 1; i <= n; i++) g[i].clear();
	}
	bool check() {
		for (auto to : g[m]) {
			if (to == t) return 1;
		}
		return 0;
	}
	int get() {
		#ifdef IOI2018
			freopen ("in.txt", "r", stdin);
		#endif
		Kazakhstan
		cin >> n >> t >> m;
		if (m == t) {
			assert(0);
			cout << 0, ioi
		}
		prep();
		for (int i = 1; i < n; i++) {
			int v, u;
			cin >> v >> u;
			g[v].pb(u);
			g[u].pb(v);
		}
		if (!check()) {
			cerr << "Incorrect test";
			ioi
		}
		dfs();
		return calc();
	}
};

auto it = solve();

int get(int x) {
	return rand() % x + 1;
}
vector <int> g[N];
void gen() {
	int n = get(7);
	if (n == 1) n++;
	for (int i = 1; i <= n; i++) g[i].clear();

	for (int i = 2; i <= n; i++) {
		int p = get(i - 1);
		g[p].pb(i);
		g[i].pb(p);
	}

	ofstream out ("in.txt");

	out << n << ' ';
	while (1) {
		int t = get(n);
		if (!sz(g[t])) continue;
		int p = get(sz(g[t]));
		out << t << ' ' << g[t][p - 1] << nl;
		//cerr << n << ' ' << t << ' ' << g[t][p - 1] << nl;
		break;
	}
	for (int i = 1; i <= n; i++) {
		for (auto to : g[i]) {
			if (i < to) {
				out << i << ' ' << to << nl;
				//cerr << i << ' ' << to << nl;
			}
		}
	}
	out.close();
}

int main() {
	cout << it.get();

	ioi

	while (1) {
		int seed = time(0); 
		srand(seed);
		for (int i = 1; i <= 100; i++) {
			gen();
			if (it.get() > 4) {
				cerr << "seed -> " << seed << " " << "test -> " << i << endl;
				cerr << it.get();
				ioi
			}
		}
	}
	ioi
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35