Submission #468812

#	Time	Username	Problem	Language	Result	Execution time	Memory
468812		wdjpng	Mousetrap (CEOI17_mousetrap)	C++17	0 / 100	424 ms	78544 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);
    }
}

vector<int>f;

int get(int k)
{
    k++;
    int sum =0;
    for(int i = k; i>0;i-=i&-1) sum+=f[i];
    return sum;
}

void update(int k)
{
    k++;
    for(int i = k; i<f.size(); i+=i&-i) f[i]++;
}

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));
    
    int maxx = 0;
    f.assign(n+1, 0);
    for(auto cost : costs)
    {
        if(get(cost.second)<cost.second+1) maxx=max(maxx, cost.first);
        else update(cost.second);
    }
    cout<<maxx<<"\n";
}

Compilation message (stderr)

mousetrap.cpp: In function 'void update(long long int)':
mousetrap.cpp:67:21: 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]
   67 |     for(int i = k; i<f.size(); i+=i&-i) f[i]++;
      |                    ~^~~~~~~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:101: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]
  101 |         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++)
......
  105 |     rep(i, path.size())
      |         ~~~~~~~~~~~~~~             
mousetrap.cpp:105:5: note: in expansion of macro 'rep'
  105 |     rep(i, path.size())
      |     ^~~
mousetrap.cpp:110: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]
  110 |             if((i>0&&w==path[i-1]||(i+1<path.size()&&w==path[i+1]))||w==t) continue;
      |                                     ~~~^~~~~~~~~~~~
mousetrap.cpp:110:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  110 |             if((i>0&&w==path[i-1]||(i+1<path.size()&&w==path[i+1]))||w==t) continue;

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