Submission #88897

#	Time	Username	Problem	Language	Result	Execution time	Memory
88897		saxeli69	Triumphal arch (POI13_luk)	C++14	100 / 100	1366 ms	24188 KiB

luk

#include <bits/stdc++.h>
using namespace std;


int  rec( int  from  , int   now , int num , vector<int>  vec[]){
   
    
    int checker = 0;
    int workersNeeded = 0 ; 
        for(int i = 0 ; i<vec[now].size() ; i++){
            if(vec[now][i]!=from){
            workersNeeded+=rec(now,vec[now][i] ,num ,vec );
            checker++;
            }
        }
        int result  = workersNeeded -  (num-checker);
    if(result   >=0)
        return result;
    return 0;
    
}
  

int main()
{
    ios::sync_with_stdio(0); 
    vector<int> vec[300001];
    int n , num2,  num1 ;
    cin>>n;
    for(int i = 0 ; i<n-1  ; i++){
        cin>>num1>>num2;
        vec[num1].push_back(num2);
        vec[num2].push_back(num1);
        
    }
    int min = 300000 ;
    int x; 
    int start = vec[1].size();
    int end = 300001 ;
    while (start <= end){
        x = (start+end)/2;
        if(rec(-1, 1 , x, vec )>0){
            start = x+1;
        }else{
             if(x<min)
                min = x ;
           end= x-1;
        }
        
        
    }
    cout<<min;
    

    return 0;
}

Compilation message (stderr)

luk.cpp: In function 'int rec(int, int, int, std::vector<int>*)':
luk.cpp:10:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0 ; i<vec[now].size() ; i++){
                         ~^~~~~~~~~~~~~~~~

• 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