제출 #1143521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143521		hhvb	Triumphal arch (POI13_luk)	C++20	100 / 100	367 ms	25688 KiB

luk

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 300001;

queue<int> q;
vector<int> adj[Nmax];
vector< pair<int, int> > v;
int adancime[Nmax];
long long dp[Nmax];
bool used[Nmax];

int main()
{
    int n, son, nod, v1, u, i, j, adancim;
    int l, r, k;

    cin >> n;
    for ( i = 0; i < n - 1; i ++ ) {
      cin >> u >> v1;
      adj[u].push_back( v1 );
      adj[v1].push_back( u );
    }

    q.push( 1 );
    used[1] = true;
    v.push_back( make_pair (0, 1) );
    while ( !q.empty() ) {
      nod = q.front();
      for ( i = 0; i < adj[nod].size(); i ++ ) {
        v1 = adj[nod][i];
        if ( used[v1] == false ) {
            q.push( v1 );
            used[v1] = true;
            adancime[v1] = adancime[nod] + 1;
            v.push_back( {adancime[v1], v1 } );
        }
      }
      q.pop();
    }

    sort ( v.begin(), v.end() );

    l = -1;
    r = Nmax - 1;
    while ( l < r - 1 ) {
      k = ( l + r ) / 2;

      for ( i = v.size() - 1; i >= 0; i -- ) {
        nod = v[i].second;
        adancim = v[i].first;
        dp[nod] = 0;
        for ( j = 0; j < adj[nod].size(); j ++ )
          if ( adancime[ adj[nod][j] ] > adancim )
            dp[nod] = dp[nod] + dp[ adj[nod][j] ] + 1;
        dp[nod] -= k;
        if ( dp[nod] < 0 ) {
          dp[nod] = 0;
        }
      }

      if ( dp[1] > 0 )
        l = k;
      else
        r = k;
    }

    cout << r << "\n";
    return 0;
}

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