Submission #1353566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1353566		goulthen	Mousetrap (CEOI17_mousetrap)	C++20	In queue	0 ms	0 KiB

mousetrap

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,a,b) for (int i = a; i >= b; i--)
#define pii pair<int,int>
#define fi first
#define se second
#define endl '\n'
#define pb push_back
#define all(v) (v).begin(), (v).end()

const int MAXN = 10;
const int INF = 1e18+10;
const int MOD = 1e9+7;
vector<pii> g[MAXN+5];
int dp[MAXN+5][(1<<MAXN)][(1<<MAXN)],n,T;

int dfs(int u, int blocked, int trail) {
    if(u==T) return 0;
    if(dp[u][blocked][trail] != -1) return dp[u][blocked][trail];
    int best = INF;
    dp[u][blocked][trail] = best;

    auto mouse_move = [&](int bl, int tr) -> int {
        int mx = -1;
        for (auto &[v,j] : g[u]) {
            if ((bl>>j&1) || (tr>>j&1)) continue;
            mx = max(mx, dfs(v, bl, tr|(1<<j)));
        }
        return mx;
    };

    {
        int mx = mouse_move(blocked, trail);
        if (mx >= 0) best = min(best, mx);
    }

    rep(i,0,n-2) {
        if(blocked>>i&1) continue;
        int nb = blocked|(1<<i);
        int mx = mouse_move(nb, trail);
        if(mx!=-1) best = min(best,mx+1);
        else best = min(best, dfs(u,nb,trail)+1);
    }
    rep(i, 0, n-2) {
        if (!(trail>>i&1)) continue;
        int nt = trail^(1<<i);
        int mx = mouse_move(blocked, nt);
        if (mx >= 0) best = min(best, mx + 1);
        else best = min(best, dfs(u, blocked, nt) + 1);
    }
    dp[u][blocked][trail] = best;
    return dp[u][blocked][trail];
}

void solve() {
    int m; cin >> n >> T >> m;
    rep(i,0,n-2) {
        int u,v; cin >> u >> v;
        g[u].pb({v,i});
        g[v].pb({u,i});
    }
    memset(dp,-1,sizeof(dp));

    cout << dfs(m,0,0) << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
	int tt = 1;
    //cin >> tt;
    
    while(tt--) solve();
}