Submission #162719

#	Time	Username	Problem	Language	Result	Execution time	Memory
162719		HellAngel	Mousetrap (CEOI17_mousetrap)	C++14	0 / 100	420 ms	92152 KiB

mousetrap

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 7;
int FastIn()
{
    char c;
    while(true)
    {
        c = getchar();
        if(c >= '0' && c <= '9') break;
    }
    int ans = c- '0';
    while(true)
    {
        c = getchar();
        if(c > '9' || c < '0') return ans;
        ans = ans * 10 + c - '0';
    }
}
int n, m, t, cnt, sum, dp[maxn], cur[maxn];

vector<int> st;

bool found;
vector<int> vt[maxn], path, gau[maxn];

void DFS(int u, int p)
{
    if(u == t)
    {
        path.push_back(u);
        found = true;
        return;
    }
    for(auto v: vt[u])
    {
        if(v == p) continue;
        DFS(v, u);
        if(found)
        {
            path.push_back(u);
            break;
        }
    }
}

void Solve(int u, int p)
{
    vector<int> cac = {};
    int sum = -1;
    for(auto v: vt[u])
    {
        if(v == p) continue;
        Solve(v, u);
        sum++;
        cac.push_back(dp[v]);
    }
    sort(cac.begin(), cac.end());
    if(cac.size())
    {
        cac.pop_back();
        if(cac.size() == 0) dp[u] = 1;
        else dp[u] = sum + cac.back() + 1;
    }
    else dp[u] = 0;
}

bool Check(int x)
{
    st = {};
    for(int i = 0; i + 1 < path.size(); i++)
    {
        cur[i + 1] = (int)gau[i + 1].size() - 1;
        int u = path[i];
        for(auto v: vt[u])
        {
            if(v == path[i + 1]) continue;
            if(i > 0 && v == path[i - 1]) continue;
            if(dp[v] > x) st.push_back(i + 1);
        }
    }
    int cnt = path.size() - 1;
    sort(st.begin(), st.end(), greater<int>());
    for(int i = 1; i <= cnt; i++)
    {
        if(st.empty()) return true;
        cur[st.back()]--;
        st.pop_back();
        if(cur[i] >= 0 && gau[i][cur[i]] > x) return false;

    }
    return true;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
    cin >> n >> m >> t;
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        vt[u].push_back(v);
        vt[v].push_back(u);
    }
    DFS(m, m);
    reverse(path.begin(), path.end());
    for(int i = 0; i + 1 < path.size(); i++)
    {
        gau[i + 1] = {};
        int u = path[i];
        for(auto v: vt[u])
        {
            if(v == path[i + 1]) continue;
            if(i > 0 && v == path[i - 1]) continue;
            Solve(v, u);
            sum++;
            gau[i + 1].push_back(dp[v]);
        }
        sort(gau[i + 1].begin(), gau[i + 1].end());
    }
    int l = 0;
    int r = 1e6;
    while(l <= r)
    {
        int mid = l + r >> 1;
        if(Check(mid)) r = mid - 1;
        else l = mid + 1;
    }
    cout << sum + l;
}

Compilation message (stderr)

mousetrap.cpp: In function 'bool Check(int)':
mousetrap.cpp:71:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i + 1 < path.size(); i++)
                    ~~~~~~^~~~~~~~~~~~~
mousetrap.cpp: In function 'int32_t main()':
mousetrap.cpp:110:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i + 1 < path.size(); i++)
                    ~~~~~~^~~~~~~~~~~~~
mousetrap.cpp:128:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
mousetrap.cpp:99:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:99:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

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