oj.uz

Submission #1102180

# Submission time Handle Problem Language Result Execution time Memory
1102180 2024-10-17T15:38:58 Z hiepsimauhong Dynamite (POI11_dyn) C++17
0 / 100
 874 ms 31804 KB 
#include <bits/stdc++.h>

using namespace std;

const int64_t oo = 1e18;

#define quickly ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define print(a,l,r) for(int OK(l); OK <= r ; ++OK){ if(a[OK] < oo){cout << a[OK] <<' ';} else{cout << "- ";}} cout << '\n';
#define prints(a) for(auto i : a){ cout << i <<' ';} cout << '\n';
#define printz(a,l,r) for(int OK(1) ; OK <= l ; ++OK){for(int KO(1) ; KO <= r ; ++KO){if(a[OK][KO] < oo){cout << a[OK][KO] <<' ';}else{cout << "- ";}}cout << '\n';} cout << '\n';
#define fs first
#define sd second
#define ii pair<int, int>
#define iii pair<int, ii>
#define all(a) a.begin(), a.end()

const int N = 3e5 + 5;
const int mod = 1e9 + 7;
const int lg = 17;

int n, m, cnt(0);
bool bom[N];
int mx_high[N];
vector<int> a[N];

void DFS(int u, int par, int mx){
      if(cnt > m){
            return;
      }
      mx_high[u] = 0;
      for(int v : a[u]){
            if(v == par){
                  continue;
            }
            DFS(v, u, mx);
            mx_high[u] = max(mx_high[u], mx_high[v] + 1);
      }
      if(mx_high[u] > mx){
            mx_high[u] = 0;
            ++cnt;
      }
}

signed main(){ quickly
      cin >> n >> m;

      for(int i(1) ; i <= n ; ++i){
            cin >> bom[i];
      }

      for(int i(1) ; i < n ; ++i){
            int u, v;
            cin >> u >> v;
            a[u].push_back(v);
            a[v].push_back(u);
      }

      int l = 1, r = n;
      int ans = 0;
      while(l <= r){
            int mid = (l + r) >> 1;
            cnt = 0;
            DFS(1, -1, mid);
            if(cnt > m){
                  l = mid + 1;
            }
            else{
                  r = mid - 1;
                  ans = mid;
            }
      }
      cout << ans;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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