oj.uz

Submission #469376

# Submission time Handle Problem Language Result Execution time Memory
469376 2021-08-31T16:26:44 Z ivan_tudor Mousetrap (CEOI17_mousetrap) C++14
0 / 100
 368 ms 67540 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int dp[N];
int h[N];
bool viz[N];
vector<int> gr[N];
int par[N];
void first_dfs(int nod, int dad){
  par[nod] = dad;
  h[nod] = 1 + h[dad];
  for(auto x:gr[nod]){
    if(x != dad)
      first_dfs(x, nod);
  }
}
void dfs(int nod, int dad){
  int nrvec = 0;
  for(auto x:gr[nod]){
    if(x == dad || viz[x] == true)
      continue;
    nrvec++;
    dfs(x, nod);
  }
  if(nrvec == 1){
    dp[nod] = 1;
    return;
  }
  int m1 = 0, m2 = 0;
  for(auto x:gr[nod]){
    if(x == dad || viz[x])
      continue;
    if(nrvec + dp[x] > m1){
      m2 = m1;
      m1 = nrvec +  dp[x];
    }
    else if(nrvec +  dp[x] > m2){
      m2 = nrvec +  dp[x];
    }
  }
  dp[nod] = m2;
}
vector<pair<int, int>> v;
int last;
int solve(int nod, int climbed){
  viz[nod] = true;
  if(par[nod] == 0)
    return 0;
  int sum = solve(par[nod], climbed + 1);
  sum += gr[nod].size() - (par[nod] != 0) - (nod != last);
  vector<int> vec;
  for(auto x:gr[nod]){
    if(viz[x] == false){
      dfs(x, nod);
      v.push_back({climbed + 1, dp[x] + sum});
    }
  }
  return sum;
}
bool check(int t){
  int cur = 0;
  for(auto x:v){
    if(x.second + cur > t){
      if(x.first > cur)
        return false;
      cur++;
    }
  }
  return true;
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n, root, m;
  cin>>n>>root>>m;
  for(int i =1 ; i<n; i++){
    int x, y;
    cin>>x>>y;
    gr[x].push_back(y);
    gr[y].push_back(x);
  }
  first_dfs(root, 0);
  last = m;
  solve(m, 0);
  sort(v.begin(), v.end());
  int ans = 0;
  for(int pas = 1<<30; pas > 0; pas /=2 ){
    if(check(ans + pas) == false)
      ans+=pas;
  }
  if(check(ans) == false)
    ans++;
  cout<<ans;
  return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23760 KB Output is correct
2 Correct 13 ms 23740 KB Output is correct
3 Correct 13 ms 23776 KB Output is correct
4 Incorrect 13 ms 23756 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23760 KB Output is correct
2 Correct 13 ms 23740 KB Output is correct
3 Correct 13 ms 23776 KB Output is correct
4 Incorrect 13 ms 23756 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23760 KB Output is correct
2 Correct 13 ms 23740 KB Output is correct
3 Correct 13 ms 23776 KB Output is correct
4 Incorrect 13 ms 23756 KB Output isn't correct
5 Halted 0 ms 0 KB -