Submission #1143375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143375		Luca7	Triumphal arch (POI13_luk)	C++20	0 / 100	407 ms	19792 KiB

luk

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

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

vector<vector<int>> graph;
vector<pair<int,int>> vval;
vector<int> vlev;

int maxl=0;

int dfs(int p,int u){
    int val=-1,vv=-1;
    for(auto v:graph[u]){
        if(p!=v){
            int nr=dfs(u,v);
            if(val<nr){
                val=nr;
                vv=v;
            }
        }
    }
    int nr=graph[u].size()-1;
    val=max(val,nr);
    vval[u]={val,vv};
    return val;
}


bool testk(int n,int k){
    vector<int> vlev1=vlev;
    for(int l=0;l<=n;l++){
        int nr=k;
        if(vlev1[l]>0){
            return false;
        }
        for(int i=l+1;i<=n;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);
    vval.resize(n+1);
    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);
    vlev.push_back(0);
    u=1;
    while(u!=-1){
        vlev.push_back(vval[u].first);
        u=vval[u].second;
    }
    for(i=1;i<=n;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