oj.uz

Submission #161189

# Submission time Handle Problem Language Result Execution time Memory
161189 2019-11-01T11:23:56 Z Minnakhmetov Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 321 ms 56172 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 << 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;
            // if (x == 2 && y == 0 && z == 0) {
            //     cout << e.to + 1 << " " << dfs(x, y | (1 << e.i), e.to) << "\n";
            // }
            ans = max(ans, dfs(x, y | (1 << e.i), e.to));
        }
    }

    // if (vector<int>{x, y, z} == vector<int>{2, 0, 0}) {
    //     cout << "!\n";
    // }

    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});
    }

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

    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 20856 KB Output is correct
2 Correct 233 ms 21004 KB Output is correct
3 Correct 321 ms 20984 KB Output is correct
4 Incorrect 45 ms 8688 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 213 ms 56172 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 27 ms 20856 KB Output is correct
2 Correct 233 ms 21004 KB Output is correct
3 Correct 321 ms 20984 KB Output is correct
4 Incorrect 45 ms 8688 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 20856 KB Output is correct
2 Correct 233 ms 21004 KB Output is correct
3 Correct 321 ms 20984 KB Output is correct
4 Incorrect 45 ms 8688 KB Output isn't correct
5 Halted 0 ms 0 KB -