Submission #468742

#	Time	Username	Problem	Language	Result	Execution time	Memory
468742		wdjpng	Mousetrap (CEOI17_mousetrap)	C++17	25 / 100	897 ms	70752 KiB

mousetrap

#include <bits/stdc++.h>
//#define double double
#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()

using namespace std;
vector<vector<int>>E;
int t,m;


int dfs(int v, int p)
{
    priority_queue<int>pq;
    int children = 0;
    for(int w : E[v])
    {
        if(w==p||w==t) continue; 
        children++;
        pq.push(-dfs(w,v));
        if(pq.size()>2) pq.pop();
    }

    int sum = min((int)1, children); //block biggest child
    if(children>1)
    {
        sum-=pq.top()-1; // cost of second biggest child + cleaning
        sum+=children-2; // block children 3 .. children
    }
    return sum;
}
vector<int>path;
vector<int>par;
void find_path(int v)
{
    if(v==m)
    {
        while (v!=t)
        {
           path.push_back(v); 
            v = par[v];
        }
        
        return;
    }
    for(int w : E[v])
    {
        if(w==par[v]) continue;
        par[w]=v;
        find_path(w);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin>>n>>t>>m;
    t--;
    m--;
    if(t==m)
    {
        cout<<0<<"\n";
        exit(0);
    }
    E.resize(n);
    par.assign(n, -1);

    rep(i, n-1)
    {
        int a,b;
        cin>>a>>b;
        a--;b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }
    find_path(t);
    //path from mouse to trap;
    vector<int>suff(path.size());
    for(int i = path.size()-1; i>=0; i--)
    {
        suff[i] = E[path[i]].size()-1;
        if(i<path.size()-1) suff[i]+=suff[i+1]-1;
    }

    vector<pair<int, int>>costs;
    rep(i, path.size())
    {
        int v = path[i];
        for(int w : E[v])
        {
            if((i>0&&w==path[i-1]||(i+1<path.size()&&w==path[i+1]))||w==t) continue;
            int c = dfs(w, v) + suff[i]; // suff because all except that edge need to be blocked and that edge needs to be cleaned
            costs.push_back({c, i});
        }
    }

    sort(all(costs));
    reverse(all(costs));

    vector<vector<int>>costs2;
    rep(i,min(path.size(), costs.size()))
    {
        costs2.push_back({costs[i].second, -costs[i].first});
    }
    sort(all(costs2));
    rep(i, costs2.size())
    {
        if(costs2[i][0] < i)
        {
            cout<<-costs2[i][1]<<"\n";
            exit(0);
        }
    }
    if(costs.size()>path.size())
    {
        cout<<costs[path.size()].first<<"\n";
        exit(0);
    }
    cout<<0<<"\n";
}

Compilation message (stderr)

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:85:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         if(i<path.size()-1) suff[i]+=suff[i+1]-1;
      |            ~^~~~~~~~~~~~~~
mousetrap.cpp:4:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,n) for(int i = 0; i < n; i++)
......
   89 |     rep(i, path.size())
      |         ~~~~~~~~~~~~~~             
mousetrap.cpp:89:5: note: in expansion of macro 'rep'
   89 |     rep(i, path.size())
      |     ^~~
mousetrap.cpp:94:40: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             if((i>0&&w==path[i-1]||(i+1<path.size()&&w==path[i+1]))||w==t) continue;
      |                                     ~~~^~~~~~~~~~~~
mousetrap.cpp:94:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   94 |             if((i>0&&w==path[i-1]||(i+1<path.size()&&w==path[i+1]))||w==t) continue;
mousetrap.cpp:4:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'const long unsigned int' [-Wsign-compare]
    4 | #define rep(i,n) for(int i = 0; i < n; i++)
......
  104 |     rep(i,min(path.size(), costs.size()))
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:104:5: note: in expansion of macro 'rep'
  104 |     rep(i,min(path.size(), costs.size()))
      |     ^~~
mousetrap.cpp:4:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,n) for(int i = 0; i < n; i++)
......
  109 |     rep(i, costs2.size())
      |         ~~~~~~~~~~~~~~~~           
mousetrap.cpp:109:5: note: in expansion of macro 'rep'
  109 |     rep(i, costs2.size())
      |     ^~~

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