Submission #162217

#	Time	Username	Problem	Language	Result	Execution time	Memory
162217		HellAngel	Mousetrap (CEOI17_mousetrap)	C++14	45 / 100	1235 ms	107728 KiB

mousetrap

#include <bits/stdc++.h>
#define int long long

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];

multiset<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.clear();
    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;
            gau[i + 1].push_back(dp[v]);
            if(dp[v] >= x) st.insert(i + 1);
        }
    }
    int cnt = path.size() - 1;
    for(int i = 1; i <= cnt; i++) sort(gau[i].begin(), gau[i].end());
    for(int i = 1; i <= cnt; i++)
    {
        if(st.empty()) return true;
        st.erase(st.begin());
        if(st.empty()) return true;
        if(*st.begin() <= i) 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);
    n = FastIn();
    t = FastIn();
    m = FastIn();
    for(int i = 1; i < n; i++)
    {
        int u, v;
        u = FastIn();
        v = FastIn();
        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++)
    {
        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++;
        }
    }
    int l = 1;
    int r = 1e9;
    while(l <= r)
    {
        int mid = l + r >> 1;
        if(Check(mid)) r = mid - 1;
        else l = mid + 1;
    }
    cout << sum + r;
}

Compilation message (stderr)

mousetrap.cpp: In function 'bool Check(long long int)':
mousetrap.cpp:73: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:115:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i + 1 < path.size(); i++)
                    ~~~~~~^~~~~~~~~~~~~
mousetrap.cpp:130:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
mousetrap.cpp:101: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:101:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

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