oj.uz

Submission #468725

# Submission time Handle Problem Language Result Execution time Memory
468725 2021-08-29T13:38:38 Z Josia Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 3327 ms 524292 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define int int64_t

using namespace std;



int t; 


map<tuple<int, vector<char>, bool>, int> mem;
map<tuple<int, vector<char>, bool>, int> visited;

vector<vector<pair<int, int>>> graph; // v, id


int dp(int m, vector<char> state, bool turn) {   // state 0 = clean; 1 = dirty; 2 = blocked;
    if (m == t) return 0;
    if (mem.count({m, state, turn})) {return mem[{m, state, turn}];}
    if (visited[{m, state, turn}] > 3) return 1e15;
    visited[{m, state, turn}] += 1;



    if (turn) {   // mouse: turn = 1
        int res = -1;
        for (auto i: graph[m]) {
            vector<char> stateHere = state;
            if (state[i.second] != 0) continue;
            stateHere[i.second] = 1;
            res = max(res, dp(i.first, stateHere, !turn));
        }
        if (res == -1) res = dp(m, state, !turn);
        return mem[{m, state, turn}] = res;
    } else {
        int res = dp(m, state, !turn);

        for (int i = 0; i<state.size(); i++) {
            if (state[i] == 2) continue;
            if (state[i] == 0) {
                state[i] = 2;
                res = min(res, dp(m, state, !turn)+1);
                state[i] = 0;
            }
            if (state[i] == 1) {
                state[i] = 0;
                res = min(res, dp(m, state, !turn)+1);
                state[i] = 1;

                state[i] = 2;
                res = min(res, dp(m, state, !turn)+1);
                state[i] = 1;
            }
        }
        return mem[{m, state, turn}] = res;
    }
}



signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);


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

    vector<int> a(1, 0);

    graph.clear();
    graph.resize(n);

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

    vector<char> state(n-1, 0);
    int res = dp(m, state, 0);
    assert(res<1e5);

    cout << res  << "\n";
    

    return 0;
}

Compilation message

mousetrap.cpp: In function 'int64_t dp(int64_t, std::vector<char>, bool)':
mousetrap.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int i = 0; i<state.size(); i++) {
      |                         ~^~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 5820 KB Output is correct
2 Correct 3327 ms 54524 KB Output is correct
3 Correct 3172 ms 52924 KB Output is correct
4 Incorrect 785 ms 16516 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 2520 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 5820 KB Output is correct
2 Correct 3327 ms 54524 KB Output is correct
3 Correct 3172 ms 52924 KB Output is correct
4 Incorrect 785 ms 16516 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 5820 KB Output is correct
2 Correct 3327 ms 54524 KB Output is correct
3 Correct 3172 ms 52924 KB Output is correct
4 Incorrect 785 ms 16516 KB Output isn't correct
5 Halted 0 ms 0 KB -