oj.uz

Submission #491073

# Submission time Handle Problem Language Result Execution time Memory
491073 2021-11-30T12:50:52 Z MasterTaster Triumphal arch (POI13_luk) C++14
90 / 100
 996 ms 27772 KB 
#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define MAXN 300010

using namespace std;

int k, n, dp[MAXN];
bool bio[MAXN];
vector<int> g[MAXN];

void dfs(int u)
{
    bio[u]=true;

    for (auto v:g[u])
    {
        if (!bio[v])
        {
            dfs(v);
            dp[u]+=(dp[v]+1);
        }
    }
    dp[u]-=k;
    dp[u]=max(dp[u], 0);
}

bool check(int x)
{
    k=x;
    for (int i=1; i<=n; i++) { bio[i]=false; dp[i]=0; }
    dfs(1);
    if (dp[1]<=0) return true;
    else return false;
}

void bs()
{
    int l=1, r=n, ress=n;

    while (l<=r)
    {
        int mid=l+(r-l)/2;
        if (check(mid)) { ress=mid; r=mid-1; }
        else l=mid+1;
    }

    cout<<ress;
}

int main()
{
    cin>>n;

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

    bs();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 4 ms 7244 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 4 ms 7244 KB Output is correct
4 Correct 4 ms 7244 KB Output is correct
5 Incorrect 4 ms 7244 KB Output isn't correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 4 ms 7244 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 7740 KB Output is correct
2 Correct 15 ms 8028 KB Output is correct
3 Correct 12 ms 7856 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 8728 KB Output is correct
2 Correct 39 ms 9572 KB Output is correct
3 Correct 34 ms 8904 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 12288 KB Output is correct
2 Correct 171 ms 14084 KB Output is correct
3 Correct 82 ms 12536 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 17476 KB Output is correct
2 Correct 523 ms 22000 KB Output is correct
3 Correct 206 ms 17988 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 996 ms 22612 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 951 ms 22612 KB Output is correct
2 Correct 979 ms 27772 KB Output is correct
3 Correct 414 ms 23468 KB Output is correct