Submission #161190

#	Time	Username	Problem	Language	Result	Execution time	Memory
161190		Minnakhmetov	Mousetrap (CEOI17_mousetrap)	C++14	0 / 100	239 ms	56056 KiB

mousetrap

#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
 
using namespace std;

struct E {
    int to, i;
};

const int N = 10, M = N - 1, INF = 1e9;
int dp[1 << M][1 << M][N];
vector<E> g[N];
int n, m, t;
int used[1 << N][1 << M][N];

int dfs(int x, int y, int z);

int go(int x, int y, int z) {
    int ans = 0;

    bool impasse = true;

    for (E e : g[z]) {
        if ((((x | y) >> e.i) & 1) == 0) {
            impasse = false;
            ans = max(ans, dfs(x, y | (1 << e.i), e.to));
        }
    }

    if (impasse)
        return dfs(x, y, z);
    return ans;
}

int dfs(int x, int y, int z) {
    if (used[x][y][z] == 2)
        return dp[x][y][z];

    if (used[x][y][z] == 1)
        return INF;

    used[x][y][z] = 1;

    int ans = 0;

    if (z != t) {
        ans = go(x, y, z);
        for (int i = 0; i < n - 1; i++) {
            if (((x >> i) & 1) == 0) {
                // if (go(x | (1 << i), y, z) == 0 && (x + y) == 0) {
                //     cout << (x | 1 << i) << " " << y << " " << z << "\n";
                // }
                ans = min(ans, go(x | (1 << i), y, z) + 1);
            }
            if (((y >> i) & 1) == 1) {
                ans = min(ans, go(x, y ^ (1 << i), z) + 1);
            }
        }
    }

    dp[x][y][z] = ans;
    used[x][y][z] = 2;
    return ans;
}
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n >> t >> m;
    m--, t--;

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }

    int ans = dfs(0, 0, m);

    if (ans >= INF)
        exit(1);

    cout << ans << "\n";

    return 0;
}

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