oj.uz

Submission #467603

# Submission time Handle Problem Language Result Execution time Memory
467603 2021-08-23T19:41:24 Z idk321 Mousetrap (CEOI17_mousetrap) C++17
20 / 100
 799 ms 524288 KB 
#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, true) << "\n";
    }
}

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

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 272020 KB Output is correct
2 Correct 157 ms 271964 KB Output is correct
3 Correct 154 ms 272024 KB Output is correct
4 Correct 155 ms 272052 KB Output is correct
5 Correct 160 ms 272152 KB Output is correct
6 Correct 141 ms 272052 KB Output is correct
7 Correct 165 ms 271964 KB Output is correct
8 Correct 169 ms 272080 KB Output is correct
9 Correct 144 ms 272080 KB Output is correct
10 Correct 144 ms 272076 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 799 ms 524288 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 272020 KB Output is correct
2 Correct 157 ms 271964 KB Output is correct
3 Correct 154 ms 272024 KB Output is correct
4 Correct 155 ms 272052 KB Output is correct
5 Correct 160 ms 272152 KB Output is correct
6 Correct 141 ms 272052 KB Output is correct
7 Correct 165 ms 271964 KB Output is correct
8 Correct 169 ms 272080 KB Output is correct
9 Correct 144 ms 272080 KB Output is correct
10 Correct 144 ms 272076 KB Output is correct
11 Runtime error 405 ms 524288 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 272020 KB Output is correct
2 Correct 157 ms 271964 KB Output is correct
3 Correct 154 ms 272024 KB Output is correct
4 Correct 155 ms 272052 KB Output is correct
5 Correct 160 ms 272152 KB Output is correct
6 Correct 141 ms 272052 KB Output is correct
7 Correct 165 ms 271964 KB Output is correct
8 Correct 169 ms 272080 KB Output is correct
9 Correct 144 ms 272080 KB Output is correct
10 Correct 144 ms 272076 KB Output is correct
11 Runtime error 799 ms 524288 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -