oj.uz

Submission #654062

# Submission time Handle Problem Language Result Execution time Memory
654062 2022-10-29T17:35:11 Z MasterTaster Triumphal arch (POI13_luk) C++14
100 / 100
 991 ms 27800 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-1, ress=n-1;
 
    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 7252 KB Output is correct
2 Correct 4 ms 7264 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 5 ms 7356 KB Output is correct
3 Correct 4 ms 7356 KB Output is correct
4 Correct 5 ms 7352 KB Output is correct
5 Correct 6 ms 7356 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7764 KB Output is correct
2 Correct 13 ms 7996 KB Output is correct
3 Correct 10 ms 7764 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 8808 KB Output is correct
2 Correct 40 ms 9624 KB Output is correct
3 Correct 26 ms 8828 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 12180 KB Output is correct
2 Correct 259 ms 14108 KB Output is correct
3 Correct 88 ms 12652 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 17460 KB Output is correct
2 Correct 546 ms 22112 KB Output is correct
3 Correct 337 ms 18076 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 962 ms 22620 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 991 ms 22524 KB Output is correct
2 Correct 895 ms 27800 KB Output is correct
3 Correct 433 ms 23476 KB Output is correct