oj.uz

Submission #468737

# Submission time Handle Problem Language Result Execution time Memory
468737 2021-08-29T13:51:36 Z wdjpng Mousetrap (CEOI17_mousetrap) C++17
25 / 100
 940 ms 70796 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 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 379 ms 70796 KB Output is correct
2 Correct 344 ms 63744 KB Output is correct
3 Correct 940 ms 69104 KB Output is correct
4 Correct 393 ms 34872 KB Output is correct
5 Correct 878 ms 69048 KB Output is correct
6 Correct 885 ms 69108 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -