oj.uz

Submission #249382

# Submission time Handle Problem Language Result Execution time Memory
249382 2020-07-14T19:21:19 Z Sorting Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 790 ms 64104 KB 
#include <bits/stdc++.h>

using namespace std;

const int k_N = 1e6 + 3;

int n, t, m;
vector<int> adj[k_N];

pair<int, bool> dp[k_N];

int solve(int node, int p = -1){
    auto &[ans, solved] = dp[node];
    if(solved)
        return ans;

    solved = true;
    ans = adj[node].size() - 1;

    int max1 = 0, max2 = 0;
    for(int to: adj[node]){
        if(to == p) continue;
        if(to == t){
            ans--;
            continue;
        }

        int curr = solve(to, node);
        if(curr >= max1){
            max2 = max1;
            max1 = curr;
        }
        else if(curr >= max2) max2 = curr;
    }

    ans += max2;
    //cout << ans << " - " << node << " ans node\n";
    return ans;
}

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

    cin >> n >> t >> m;

    for(int i = 0; i < n - 1; ++i){
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    cout << solve(m, t) << "\n";
}

Compilation message

mousetrap.cpp: In function 'int solve(int, int)':
mousetrap.cpp:13:11: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     auto &[ans, solved] = dp[node];
           ^

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 23808 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 378 ms 63004 KB Output is correct
2 Correct 342 ms 59128 KB Output is correct
3 Correct 765 ms 64104 KB Output is correct
4 Correct 345 ms 43896 KB Output is correct
5 Correct 754 ms 64092 KB Output is correct
6 Correct 790 ms 63992 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 23808 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 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -