oj.uz

Submission #469340

# Submission time Handle Problem Language Result Execution time Memory
469340 2021-08-31T14:08:55 Z ivan_tudor Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 969 ms 69440 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];
multiset<int> ms;
int last;
int solve(int nod){
  viz[nod] = true;
  if(par[nod] == 0)
    return 0;
  int sum = solve(par[nod]);
  vector<int> vec;
  for(auto x:gr[nod]){
    if(viz[x] == false){
      dfs(x, nod);
      vec.push_back(dp[x]);
    }
  }
  sort(vec.begin(), vec.end());
  sum += gr[nod].size() - (par[nod] != 0) - (nod != last);
  for(int i = 0; i < vec.size(); i++){
    ms.insert(sum +  vec[i]);
  }
  ms.insert(sum);
  if(ms.size()){
    auto itr = ms.rbegin();
    ms.erase(ms.find(*itr));
  }
  if(last == nod && ms.size())
    ans = *ms.rbegin();
  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);
  last = m;
  solve(m);
  cout<<ans;
  return 0;
}

Compilation message

mousetrap.cpp: In function 'int solve(int)':
mousetrap.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for(int i = 0; i < vec.size(); i++){
      |                  ~~^~~~~~~~~~~~

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 23756 KB Output is correct
3 Correct 13 ms 23788 KB Output is correct
4 Correct 13 ms 23832 KB Output is correct
5 Correct 13 ms 23788 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 13 ms 23756 KB Output is correct
8 Correct 13 ms 23756 KB Output is correct
9 Correct 13 ms 23756 KB Output is correct
10 Correct 13 ms 23800 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 68016 KB Output is correct
2 Correct 321 ms 64032 KB Output is correct
3 Correct 926 ms 69432 KB Output is correct
4 Correct 416 ms 47300 KB Output is correct
5 Correct 963 ms 69432 KB Output is correct
6 Correct 969 ms 69440 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 23756 KB Output is correct
3 Correct 13 ms 23788 KB Output is correct
4 Correct 13 ms 23832 KB Output is correct
5 Correct 13 ms 23788 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 13 ms 23756 KB Output is correct
8 Correct 13 ms 23756 KB Output is correct
9 Correct 13 ms 23756 KB Output is correct
10 Correct 13 ms 23800 KB Output is correct
11 Correct 14 ms 23756 KB Output is correct
12 Correct 14 ms 23888 KB Output is correct
13 Correct 16 ms 23944 KB Output is correct
14 Correct 14 ms 23976 KB Output is correct
15 Correct 14 ms 23884 KB Output is correct
16 Correct 14 ms 23884 KB Output is correct
17 Incorrect 14 ms 23816 KB Output isn't correct
18 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 23756 KB Output is correct
3 Correct 13 ms 23788 KB Output is correct
4 Correct 13 ms 23832 KB Output is correct
5 Correct 13 ms 23788 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 13 ms 23756 KB Output is correct
8 Correct 13 ms 23756 KB Output is correct
9 Correct 13 ms 23756 KB Output is correct
10 Correct 13 ms 23800 KB Output is correct
11 Correct 349 ms 68016 KB Output is correct
12 Correct 321 ms 64032 KB Output is correct
13 Correct 926 ms 69432 KB Output is correct
14 Correct 416 ms 47300 KB Output is correct
15 Correct 963 ms 69432 KB Output is correct
16 Correct 969 ms 69440 KB Output is correct
17 Correct 14 ms 23756 KB Output is correct
18 Correct 14 ms 23888 KB Output is correct
19 Correct 16 ms 23944 KB Output is correct
20 Correct 14 ms 23976 KB Output is correct
21 Correct 14 ms 23884 KB Output is correct
22 Correct 14 ms 23884 KB Output is correct
23 Incorrect 14 ms 23816 KB Output isn't correct
24 Halted 0 ms 0 KB -