Submission #249963

#	Time	Username	Problem	Language	Result	Execution time	Memory
249963		Sorting	Mousetrap (CEOI17_mousetrap)	C++14	0 / 100	794 ms	65908 KiB

mousetrap

#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() - (p != -1) - 1;
    if(ans == -1)
        ans = 0;

    //cout << ans << " - " << node << " ans node before\n";

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

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

        //cout << curr << " " << node << " " << to << "\n";

        if(curr >= max1) max2 = max1, max1 = curr;
        else if(curr >= max2) max2 = curr;
    }

    if(max2 != -k_N) ans += max2;
    else if(max1 != -k_N) ans += min(max1, 1);
    //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";
}
/*
10 3 1
1 2
2 3
1 4
1 5
4 8
4 9
2 6
6 7
2 10
*/

Compilation message (stderr)

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:94:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < path.size(); ++i){
                    ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 20
• Subtask 4: 0 / 35