oj.uz

Submission #461948

# Submission time Handle Problem Language Result Execution time Memory
461948 2021-08-10T06:41:47 Z AlexLuchianov Mousetrap (CEOI17_mousetrap) C++14
25 / 100
 1134 ms 81216 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 14 ms 23792 KB Output is correct
3 Correct 14 ms 23712 KB Output is correct
4 Correct 14 ms 23800 KB Output is correct
5 Incorrect 14 ms 23756 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 80220 KB Output is correct
2 Correct 340 ms 74480 KB Output is correct
3 Correct 1059 ms 81132 KB Output is correct
4 Correct 542 ms 52316 KB Output is correct
5 Correct 1134 ms 81216 KB Output is correct
6 Correct 1085 ms 81176 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 14 ms 23792 KB Output is correct
3 Correct 14 ms 23712 KB Output is correct
4 Correct 14 ms 23800 KB Output is correct
5 Incorrect 14 ms 23756 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 14 ms 23792 KB Output is correct
3 Correct 14 ms 23712 KB Output is correct
4 Correct 14 ms 23800 KB Output is correct
5 Incorrect 14 ms 23756 KB Output isn't correct
6 Halted 0 ms 0 KB -