oj.uz

Submission #469138

# Submission time Handle Problem Language Result Execution time Memory
469138 2021-08-30T21:42:39 Z ivan_tudor Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 938 ms 71288 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;
}
int ans = 0;
int solve(int nod, int climbed){
  viz[nod] = true;
  if(par[nod] == 0)
    return 0;
  int sum = solve(par[nod], climbed + 1);
  dfs(nod, 0);
  ans = max(ans, dp[nod] - climbed + sum);
  sum += gr[nod].size() - (par[nod] != 0) - 1;
  return sum;
}
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);
  solve(m, 0);
  cout<<ans;
  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23704 KB Output is correct
3 Correct 13 ms 23824 KB Output is correct
4 Correct 13 ms 23820 KB Output is correct
5 Correct 13 ms 23816 KB Output is correct
6 Correct 13 ms 23740 KB Output is correct
7 Correct 13 ms 23748 KB Output is correct
8 Correct 15 ms 23756 KB Output is correct
9 Correct 15 ms 23760 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 66784 KB Output is correct
2 Correct 311 ms 65808 KB Output is correct
3 Correct 938 ms 71252 KB Output is correct
4 Correct 419 ms 49096 KB Output is correct
5 Correct 929 ms 71156 KB Output is correct
6 Correct 934 ms 71288 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23704 KB Output is correct
3 Correct 13 ms 23824 KB Output is correct
4 Correct 13 ms 23820 KB Output is correct
5 Correct 13 ms 23816 KB Output is correct
6 Correct 13 ms 23740 KB Output is correct
7 Correct 13 ms 23748 KB Output is correct
8 Correct 15 ms 23756 KB Output is correct
9 Correct 15 ms 23760 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct
11 Incorrect 13 ms 23756 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23704 KB Output is correct
3 Correct 13 ms 23824 KB Output is correct
4 Correct 13 ms 23820 KB Output is correct
5 Correct 13 ms 23816 KB Output is correct
6 Correct 13 ms 23740 KB Output is correct
7 Correct 13 ms 23748 KB Output is correct
8 Correct 15 ms 23756 KB Output is correct
9 Correct 15 ms 23760 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct
11 Correct 351 ms 66784 KB Output is correct
12 Correct 311 ms 65808 KB Output is correct
13 Correct 938 ms 71252 KB Output is correct
14 Correct 419 ms 49096 KB Output is correct
15 Correct 929 ms 71156 KB Output is correct
16 Correct 934 ms 71288 KB Output is correct
17 Incorrect 13 ms 23756 KB Output isn't correct
18 Halted 0 ms 0 KB -