Submission #1145759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145759		Ianis	Triumphal arch (POI13_luk)	C++20	0 / 100	285 ms	17740 KiB

luk

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 3e5+5;

int n;
vector<int> g[NMAX];
bitset<NMAX> vis;

void read() {
   cin >> n;
   for (int i = 1, x, y; i < n; i++) {
      cin >> x >> y;
      g[x].push_back(y);
      g[y].push_back(x);
   }
}

bool good(int m) {
   if (m < 0) return false;
   vis.reset();

   int cnt = 0;
   queue<pair<int, int>> q;
   q.push({ 1, 0 });
   vis[1] = true;

   while (!q.empty()) {
      auto [ x, d ] = q.front();
      q.pop();

      if (d) {
         cnt++;
         if (1ll * cnt > 1ll * d * m) {
            return false;
         }
      }

      for (auto &y : g[x]) {
         if (!vis[y]) {
            vis[y] = true;
            q.push({ y, d + 1 });
         }
      }
   }

   return true;
}

int solve() {
   int l = 0, r = n - 1;

   while (l <= r) {
      int mid = (l + r) >> 1;
      if (!good(mid)) {
         l = mid + 1;
      } else {
         r = mid - 1;
      }
   }

   return r + 1;
}

signed main() {
#ifdef LOCAL
   freopen("input.txt", "r", stdin);
#endif

   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);

   read();
   cout << solve() << endl;

   return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10