oj.uz

Submission #510725

# Submission time Handle Problem Language Result Execution time Memory
510725 2022-01-15T02:41:00 Z Monarchuwu Mousetrap (CEOI17_mousetrap) C++17
25 / 100
 894 ms 69404 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 1e6 + 16;
int n, t, m;
vector<int> g[N];

bool checksubtask2() { // It is guaranteed that a passage between rooms m and t exists.
    for (int v : g[m])
        if (v == t) return true;
    return false;
}

int dfs(int u, int p) {
    if (g[u].size() == 1) return 0; // hết đường
    if (g[u].size() == 2) return 1; // còn 1 đường nhưng sẽ bị chặn
    vector<int> res;
    for (int v : g[u]) if (v != p) {
        res.push_back(dfs(v, u) + 1); // nếu chuột chạy vào v thì min bước là ? (+1 lượt dọn phân khi quay lại)
    }
    sort(all(res), greater<int>());
    return g[u].size() - 2 + res[1]; // chặn đường thứ nhất, chuột đi vào đường thứ nhì
}
void subtask2() {
    cout << dfs(m, t) << '\n';
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> t >> m;
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    if (checksubtask2()) subtask2();
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 23756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 55088 KB Output is correct
2 Correct 378 ms 63968 KB Output is correct
3 Correct 763 ms 69288 KB Output is correct
4 Correct 368 ms 46392 KB Output is correct
5 Correct 894 ms 69404 KB Output is correct
6 Correct 837 ms 69280 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 23756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 23756 KB Output isn't correct
2 Halted 0 ms 0 KB -