Submission #46372

#	Time	Username	Problem	Language	Result	Execution time	Memory
46372		RockyB	Mousetrap (CEOI17_mousetrap)	C++17	0 / 100	220 ms	70000 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)5e5 + 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;
vector < pair <int, int> > g[N];

int a[N];

bool canGo(int v) {
	for (auto to : g[v]) {
		if (!a[to.s]) return 1;
	}
	return 0;
}

set <int> st;
int ans = inf;
void calc(int v = 0, int p = m, int d = 0) {
	if (p == t) {
		ans = min(ans, d);
		return;
		//return 0;
	}

	{
		int h = 0;
		for (int i = 1; i < n; i++) {
			h = h * 3 + a[i];
		}
		if (st.count(h)) return;
		st.insert(h);
	}

	int res = !v ? inf : -inf;
	if (!v) {
		//if (canGo(p)) res = min(res, calc(v ^ 1, p));
		for (int i = 1; i < n; i++) {
			if (a[i] != 2) {
				int s = a[i];
				a[i] = 2;
				calc(v ^ 1, p, d + 1);
				a[i] = s;
			}
			if (a[i] == 1) {
				a[i] = 0;
				calc(v + 1, p, d + 1);
				a[i] = 1;
			}
		}
	}
	else {
		for (auto to : g[p]) {
			if (!a[to.s]) {
				a[to.s] = 1;
				calc(v ^ 1, to.f, d + 1);
				a[to.s] = 0;
			}
		}
	}

	//return res;
}
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	Kazakhstan
	cin >> n >> t >> m;
	for (int i = 1; i < n; i++) {
		int v, u;
		cin >> v >> u;
		g[v].pb({u, i});
		g[u].pb({v, i});
	}
	calc();
	cout << ans;
	ioi
}

Compilation message (stderr)

mousetrap.cpp: In function 'void calc(int, int, int)':
mousetrap.cpp:68:6: warning: unused variable 'res' [-Wunused-variable]
  int res = !v ? inf : -inf;
      ^~~

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