oj.uz

Submission #469144

# Submission time Handle Problem Language Result Execution time Memory
469144 2021-08-30T22:07:02 Z ivan_tudor Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 985 ms 67940 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 sm[N];
set<pair<pair<int, int>, int>> ms;
int solve(int nod){
  viz[nod] = true;
  if(par[nod] == 0)
    return 0;
  int sum = solve(par[nod]);
  dfs(nod, 0);
  ms.insert({{sum + dp[nod], h[nod]}, nod});
  sm[nod] = sum + dp[nod];
  sum += gr[nod].size() - (par[nod] != 0) - 1;
  return sum;
}
void solvefr(int nod){
  if(par[nod] == 0)
    return;
  ans = max(ans, sm[nod]);
  ms.erase({{sm[nod], h[nod]}, nod});
  if(ms.size()){
    int id = (*ms.rbegin()).second;
    ms.erase(*ms.rbegin());
    sm[id] --;
    ms.insert({{sm[id], h[id]}, id});
  }
}
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);
  solvefr(m);
  cout<<ans;
  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23816 KB Output is correct
2 Correct 14 ms 23756 KB Output is correct
3 Correct 13 ms 23816 KB Output is correct
4 Correct 13 ms 23784 KB Output is correct
5 Correct 31 ms 23772 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 13 ms 23832 KB Output is correct
8 Correct 13 ms 23712 KB Output is correct
9 Correct 15 ms 23828 KB Output is correct
10 Correct 14 ms 23784 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 66924 KB Output is correct
2 Correct 328 ms 62428 KB Output is correct
3 Correct 985 ms 67940 KB Output is correct
4 Correct 456 ms 45848 KB Output is correct
5 Correct 979 ms 67900 KB Output is correct
6 Correct 963 ms 67884 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23816 KB Output is correct
2 Correct 14 ms 23756 KB Output is correct
3 Correct 13 ms 23816 KB Output is correct
4 Correct 13 ms 23784 KB Output is correct
5 Correct 31 ms 23772 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 13 ms 23832 KB Output is correct
8 Correct 13 ms 23712 KB Output is correct
9 Correct 15 ms 23828 KB Output is correct
10 Correct 14 ms 23784 KB Output is correct
11 Incorrect 15 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 23816 KB Output is correct
2 Correct 14 ms 23756 KB Output is correct
3 Correct 13 ms 23816 KB Output is correct
4 Correct 13 ms 23784 KB Output is correct
5 Correct 31 ms 23772 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 13 ms 23832 KB Output is correct
8 Correct 13 ms 23712 KB Output is correct
9 Correct 15 ms 23828 KB Output is correct
10 Correct 14 ms 23784 KB Output is correct
11 Correct 380 ms 66924 KB Output is correct
12 Correct 328 ms 62428 KB Output is correct
13 Correct 985 ms 67940 KB Output is correct
14 Correct 456 ms 45848 KB Output is correct
15 Correct 979 ms 67900 KB Output is correct
16 Correct 963 ms 67884 KB Output is correct
17 Incorrect 15 ms 23756 KB Output isn't correct
18 Halted 0 ms 0 KB -