Submission #1145288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145288		calisovradu	Triumphal arch (POI13_luk)	C++20	100 / 100	517 ms	27448 KiB

luk

#include <bits/stdc++.h>
using namespace std;
    vector<vector<int>> v;
    vector<long long> dp;
    vector<int> checked;

int n;
void ref(){
    for(int i=1;i<=n;i++)
    checked[i]=dp[i]=0;
}

void dfs(int node,long long crews){

    for(int i=0;i<v[node].size();i++){
        int newnode = v[node][i];

        if(checked[newnode]==0){
            checked[newnode]=1;

            dfs(newnode,crews);
            dp[node]+=dp[newnode];
            dp[node]++;
        }
    }
    if(dp[node]-crews>0)
    dp[node] = dp[node]-crews;
    else
    dp[node] = 0;

}

int main() {
    cin>>n;
    v.resize(n+1);
    dp.resize(n+1);
    checked.resize(n+1);
    
    for(int i=1;i<=n-1;i++){
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    
    long long l=0,r=n,mij,corect=n;
    while(l<=r){

        mij=(l+r)/2;
        ref();
        checked[1]=1;
        dfs(1,mij);
        
        if(dp[1]==0){
            corect=min(mij,corect);
            r=mij-1;
        }else
        l=mij+1;
    }
    cout<<corect;

}

• 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