Submission #1143388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143388		hhvb	Triumphal arch (POI13_luk)	C++20	0 / 100	418 ms	23116 KiB

luk

#include <bits/stdc++.h>

using namespace std;

queue<int> q;
vector< pair<int, int> > m;
int need[300001], h[300001];
bool used[300001];
vector<int> adj[300001];

int main()
{
    int n, u, v, adancime, k;
    int i;
    cin >> n;
    for ( i= 0; i < n - 1; i ++ ) {
        cin >> u >> v;
        adj[u].push_back( v );
        adj[v].push_back( u );
    }

    q.push( 1 );
    used[1] = true;
    m.push_back( {0, 1} );
    adancime = 0;
    h[1] = 0;
    while ( !q.empty() ) {
        u = q.front();
        for ( i = 0; i < adj[u].size(); i ++ ) {
            if ( used[ adj[u][i] ] == false ) {
                q.push( adj[u][i] );
                v = h[u] + 1;
                h [ adj[u][i] ] = v;
                m.push_back( make_pair( v, adj[u][i] ) );
                used[adj[u][i]] = true;
                if ( v > adancime )
                    adancime = v;
            }
        }
        q.pop();
    }
    sort ( m.begin(), m.end() );
    int l, r, j;
    l = 0;
    r = 300000;
    while ( l + 1 < r ) {
        k = (l + r) / 2;

        for ( i = n - 1; i >= 0; i -- ){
        u = m[i].second;
        if ( m[i].first == adancime ) {
            need[u] = 0;
        }
        else {
            for ( j = 0; j < adj[u].size(); j ++ ) {
                if ( h[ adj[u][j] ] > h[u] )
                    need[u] = need[u] + need[ adj[u][j] ] + 1;
            }
            need[u] -= k;
            if ( need[u] < 0 )
                need[u] = 0;
        }
    }
    if ( need[1] > 0 ) {
        l = k;
    }
    else {
      r = k;
    }
}


    cout << l << "\n";

    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