Submission #1143274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143274		Luca7	Triumphal arch (POI13_luk)	C++20	0 / 100	884 ms	19744 KiB

luk

#include<iostream>
#include<vector>
using namespace std;

// ifstream cin("data.in");
// ofstream cout("data.out");

vector<vector<int>> graph;
vector<int> vlev;

int maxl=0;

void dfs(int p,int u,int l){
    vlev[l]++;
    maxl=max(maxl,l);
    for(auto v:graph[u]){
        if(p!=v){
            dfs(u,v,l+1);
        }
    }
}


bool testk(int n,int k){
    vector<int> vlev1=vlev;
    for(int l=0;l<=maxl;l++){
        int nr=k;
        if(vlev1[l]>0){
            return false;
        }
        for(int i=l+1;i<=maxl;i++){
            if(vlev1[i]>0){
                if(vlev1[i]>nr){
                    vlev1[i]-=nr;
                    nr=0;
                }
                else{
                    nr-=vlev1[i];
                    vlev1[i]=0;
                }
            }
            if(nr==0){
                break;
            }
        }
    }
    return true;
}

int main(){
    int i,j,n,u,v,sum=0;

    cin>>n;
    graph.resize(n+1);
    vlev.resize(n+1,0);
    for(i=1;i<n;i++){
        cin>>u>>v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    int res=1;
    dfs(-1,1,0);
    vlev[0]=0;
    for(i=0;i<=n;i++){
        res=max(res,vlev[i]);
        sum+=vlev[i];
    }
    for(i=1;i<=res;i++){
        if(testk(n,i)){
            break;
        }
    }
    cout<<i;
    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