Submission #467601

#	Time	Username	Problem	Language	Result	Execution time	Memory
467601		idk321	Mousetrap (CEOI17_mousetrap)	C++17	0 / 100	826 ms	524288 KiB

mousetrap

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

const int N = 1000005;
vector<array<int, 2>> adj[N];
int cost[N];

int n, t, m;

void dfs(int node, int par, int height) {
    array<int, 2> most={0, 0};
    for (auto next : adj[node]) {
        if (next[0] == par) continue;
        dfs(next[0], node, height + 1);
        if (cost[next[0]] > most[1]) most[1] = cost[next[0]];
        if (most[1] > most[0]) swap(most[1], most[0]);
    }

    if (par != -1 && adj[node].size() == 1) {
        cost[node] = height - 1;
    } else if (par != -1 && adj[node].size() == 2) {
        cost[node] = height;
    } else {
        cost[node] = adj[node].size() - 2 + most[1];
    }
}

int dp[1 << 9][1 << 9][11][11][2];


int minMax(int mouse, bool el, int blocked, int dirty, int turn, bool moved) {
    if (dp[blocked][dirty][mouse][turn][el] != -1) return dp[blocked][dirty][mouse][turn][el];
    if (turn >= 10) return 10;
    if (el) {
        int best = 10;
        for (int i = 0; i < n - 1; i++) {
            if (!(dirty &  (1 << i)) && !(blocked & (1 << i))) {
                best =min(best, minMax(mouse, !el, (blocked | (1 << i)), dirty, turn + 1, false));
            }
            if (dirty & (1 << i)) {
                best = min(best, minMax(mouse, !el, blocked, (dirty ^ (1 << i)), turn + 1, false));
            }
        }
        if (moved) {
            best = min(best, minMax(mouse, !el, blocked, dirty, turn, false));
        }
        dp[blocked][dirty][mouse][turn][el] = best;
        return best;
        //best = min(best, minMax(mouse, !el, blocked, diry, turn));
    } else {
        int best = turn;
        bool travelled = false;
        for (auto next : adj[mouse]) {
            if (!(blocked & (1 << next[1]))&& !(dirty & 1 << next[1])) {
                travelled = true;
                if (next[0] != t) {
                    best = max(best, minMax(next[0], !el, blocked, (dirty | (1 << next[1])), turn, true));
                }
            }
        }
        if (!travelled) best = max(best, minMax(mouse, !el, blocked, dirty, turn, false));
        dp[blocked][dirty][mouse][turn][el] = best;
        bitset<9> a(blocked);
        bitset<9> b(dirty);


        return best;
    }

}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> t >> m;
    bool connected = false;
    for (int i = 0; i < (1 << 9); i++) {
        for (int j = 0; j < (1 << 9); j++) {
            for (int k = 0; k < 11; k++) {
                for (int l = 0; l < 11; l++) {
                    for (int m = 0; m < 2; m++) dp[i][j][k][l][m] = -1;
                }
            }
        }
    }
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }
    if (false/*(a == t && b == m) || (a == m && b == t)*/) {
            dfs(t, -1, 0);
            cout << cost[m] << "\n";
    } else {
        cout << minMax(m, true, 0, 0, 0, false) << "\n";
    }
}

/*
10 1 2
1 2
2 3
2 4
3 9
3 5
4 7
4 6
6 8
7 10
*/

Compilation message (stderr)

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:79:10: warning: unused variable 'connected' [-Wunused-variable]
   79 |     bool connected = false;
      |          ^~~~~~~~~

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