Submission #1143144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143144		Gtudor	Triumphal arch (POI13_luk)	C++20	0 / 100	152 ms	18484 KiB

luk

#include <iostream>
#include <vector>

#define NMAX 300000

using namespace std;

int dist[NMAX + 1], f[NMAX + 1];

vector<int>edge[NMAX + 1];

void dfs(int p, int nod) {
  for(auto vecin : edge[nod]) {
    if(vecin == p)
      continue;
    dist[vecin] = dist[nod] + 1;
    f[dist[vecin]]++;
    dfs(nod, vecin);
  }
}

int main() {
  int n, a, b, mx = 0, builduri = 0, st, dr, mij;
  cin>>n;
  for(int i = 1; i < n; i++) {
    cin>>a>>b;
    edge[a].push_back(b);
    edge[b].push_back(a);
  }
  dfs(0, 1);
  st = 0;
  dr = n;
  int last = 0;
  while(st <= dr) {
    mij = (st + dr) / 2;
    bool ok = 1;
    builduri = 0;
    for(int i = 0; i <= n; i++) {
      builduri -= f[i];
      if(builduri < 0) {
        ok = 0;
        break;
      }
      builduri += mij;
    }
    if(ok) {
      last = mij;
      dr = mij - 1;
    } else {
      st = mij + 1;
    }
  }
  cout<<last;
  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