oj.uz

Submission #161191

# Submission time Handle Problem Language Result Execution time Memory
161191 2019-11-01T11:31:31 Z Minnakhmetov Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 233 ms 55928 KB 
#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 << M][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) {
                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});
    }

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

    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 20728 KB Output is correct
2 Correct 233 ms 21112 KB Output is correct
3 Correct 198 ms 20876 KB Output is correct
4 Incorrect 41 ms 8540 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 208 ms 55928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 20728 KB Output is correct
2 Correct 233 ms 21112 KB Output is correct
3 Correct 198 ms 20876 KB Output is correct
4 Incorrect 41 ms 8540 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 20728 KB Output is correct
2 Correct 233 ms 21112 KB Output is correct
3 Correct 198 ms 20876 KB Output is correct
4 Incorrect 41 ms 8540 KB Output isn't correct
5 Halted 0 ms 0 KB -