oj.uz

Submission #249420

# Submission time Handle Problem Language Result Execution time Memory
249420 2020-07-14T22:46:09 Z Sorting Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 776 ms 64128 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];
bool in_path[k_N];
int pos[k_N];
vector<int> path;
int sz[k_N];

bool dfs(int node, int end, int p = -1){
    if(node == end){
        path.push_back(node);
        in_path[node] = true;
        return true;
    }
    for(int to: adj[node]){
        if(to == p) continue;
        if(dfs(to, end, node)){
            path.push_back(node);
            in_path[node] = true;
            return true;
        }
    }
    return false;
}

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

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

    int max1 = 0, max2 = 0;
    for(int to: adj[node]){
        if(to == p || (in_path[node] && to == path[pos[node] + 1]))
            ans--;
        if(to == p || to == t) continue;

        int curr = solve(to, node);
        if(in_path[node] && to != path[pos[node] + 1])
            curr += sz[pos[node] + 1];

        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;

    if(t == m){
        cout << "0\n";
        return 0;
    }

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

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

    dfs(m, t);
    reverse(path.begin(), path.end());

    /*cout << "path: ";
    for(int x: path)
        cout << x << " ";
    cout << "\n";*/

    for(int i = 0; i < path.size(); ++i){
        int x = path[i];
        pos[x] = i;
        if(x == t) sz[i] = 0;
        else if(x == m) sz[i] = adj[x].size() - 1;
        else sz[i] = adj[x].size() - 2;
    }

    for(int i = path.size() - 2; i >= 0; --i) 
        sz[i] += sz[i + 1];

    cout << solve(m) << "\n";
}
/*
7 3 1
1 2
2 3
1 4
1 5
2 6
2 7
*/

Compilation message

mousetrap.cpp: In function 'int solve(int, int)':
mousetrap.cpp:34:11: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     auto &[ans, solved] = dp[node];
           ^
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:90:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < path.size(); ++i){
                    ~~^~~~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 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 355 ms 63056 KB Output is correct
2 Correct 341 ms 59000 KB Output is correct
3 Correct 760 ms 64124 KB Output is correct
4 Correct 365 ms 43896 KB Output is correct
5 Correct 765 ms 64120 KB Output is correct
6 Correct 776 ms 64128 KB Output is correct

Subtask #3
0 / 20.0

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