Submission #461948

#	Time	Username	Problem	Language	Result	Execution time	Memory
461948		AlexLuchianov	Mousetrap (CEOI17_mousetrap)	C++14	25 / 100	1134 ms	81216 KiB

mousetrap

#include <iostream>
#include <vector>
#include <algorithm>

using ll = long long;

int const nmax = 1000000;
std::vector<int> g[1 + nmax];
int dists[1 + nmax], distt[1 + nmax];
int coef[1 + nmax];

void computecoef(int node, int parent) {
  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][h];
    if(to != parent) {
      distt[to] = distt[node] + 1;
      if(parent == 0)
        coef[to] = 0;
      else
        coef[to] = coef[node] + g[node].size() - 2;
      computecoef(to, node);
    }
  }
}
int dp[1 + nmax];
int t, s;

void solve(int node, int parent) {
  if(node == t) {
    dp[node] = 0;
    return ;
  }

  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][h];
    if(to != parent) 
      solve(to, node);
  }
  //I block nothing
  int idmax = 0, valmax = -1;
  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][h];
    if(to != parent) {
      int newcost = dp[to];
      if(parent != 0) {
        if(distt[parent] + 1 == distt[node])
          newcost++;
        else {
          if(distt[node] + 1 == distt[to])
            newcost--;
        }
      }
      if(valmax < newcost) {
        valmax = newcost;
        idmax = to;
      }
    }
  }
  int valmax2 = -1;
  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][h];
    if(to != parent && to != idmax) {
      int newcost = dp[to] + 1;
      if(parent != 0) {
        if(distt[parent] + 1 == distt[node])
          newcost++;
        else {
          if(distt[node] + 1 == distt[to])
            newcost--;
        }
      }
      if(distt[idmax] + 1 == distt[node])
        newcost++;
      else {
        if(distt[node] + 1 == distt[to])
          newcost--;
      }
      if(valmax2 < newcost)
        valmax2 = newcost;
    }
  }

  if(0 <= valmax) {
    dp[node] = valmax;
    if(0 <= valmax2)
      dp[node] = std::min(dp[node], valmax2);
    else {
      valmax2 = coef[node] + 1;
      if(parent != 0 && distt[parent] + 1 == distt[node])
        valmax2++;
      if(distt[idmax] + 1 == distt[node])
        valmax2++;
      dp[node] = std::min(dp[node], valmax2);
    }
  } else {
    dp[node] = coef[node];
    if(parent != 0 && distt[parent] + 1 == distt[node])
      dp[node]++;
  }
}

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n;
  std::cin >> n >> t >> s;
  for(int i = 1;i < n; i++) {
    int a, b;
    std::cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  computecoef(t, 0);
  solve(s, 0); 
  std::cout << dp[s] << '\n';
  return 0;
}

Compilation message (stderr)

mousetrap.cpp: In function 'void computecoef(int, int)':
mousetrap.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~
mousetrap.cpp: In function 'void solve(int, int)':
mousetrap.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~
mousetrap.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~
mousetrap.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~

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