Submission #1143320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143320		wizard_49	Triumphal arch (POI13_luk)	C++20	0 / 100	200 ms	42104 KiB

luk

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int NMAX=300000;

vector <int> g[NMAX+1];
vector <int> tree_dist[NMAX+1];
vector <int> depth_measure[NMAX+1];
bool viz[NMAX+1];
int available_worker_teams;
int current_dist_from_base;

void dfs(int x,int dist){
    viz[x]=1;
    depth_measure[dist].push_back(x);
    for(const int &y:g[x])
        if(viz[y]==0)
        {
            tree_dist[y].push_back(dist+1);
            if(current_dist_from_base<dist+1)
                current_dist_from_base=dist+1;
            dfs(y,dist+1);
        }
}


int main()
{
    int a,b,n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1,0);
    int initial_worker_teams=depth_measure[0].size();
    int level_worker_teams,extra_worker_teams=0;
    for(int i=1;i<=current_dist_from_base;i++)
    {
        level_worker_teams=depth_measure[i].size();
        if(level_worker_teams-extra_worker_teams>=initial_worker_teams)
        {
            initial_worker_teams=level_worker_teams-extra_worker_teams;
            extra_worker_teams=0;
        }
        else if(initial_worker_teams>level_worker_teams)
            extra_worker_teams+=initial_worker_teams-level_worker_teams;
        else if(initial_worker_teams>level_worker_teams-extra_worker_teams && initial_worker_teams<level_worker_teams)
            extra_worker_teams-=initial_worker_teams-level_worker_teams;
    }
    cout<<initial_worker_teams;

    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