oj.uz

Submission #88897

# Submission time Handle Problem Language Result Execution time Memory
88897 2018-12-09T18:41:50 Z saxeli69 Triumphal arch (POI13_luk) C++14
100 / 100
 1366 ms 24188 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7516 KB Output is correct
2 Correct 7 ms 7536 KB Output is correct
3 Correct 7 ms 7708 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7708 KB Output is correct
2 Correct 7 ms 7708 KB Output is correct
3 Correct 7 ms 7708 KB Output is correct
4 Correct 7 ms 7708 KB Output is correct
5 Correct 9 ms 7708 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7708 KB Output is correct
2 Correct 9 ms 7708 KB Output is correct
3 Correct 9 ms 7708 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7708 KB Output is correct
2 Correct 11 ms 7708 KB Output is correct
3 Correct 8 ms 7708 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7904 KB Output is correct
2 Correct 17 ms 8176 KB Output is correct
3 Correct 14 ms 8176 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 8576 KB Output is correct
2 Correct 38 ms 9796 KB Output is correct
3 Correct 25 ms 9796 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 10992 KB Output is correct
2 Correct 187 ms 13308 KB Output is correct
3 Correct 74 ms 13308 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 736 ms 14312 KB Output is correct
2 Correct 525 ms 20088 KB Output is correct
3 Correct 160 ms 20088 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 891 ms 20088 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1171 ms 20088 KB Output is correct
2 Correct 1366 ms 24188 KB Output is correct
3 Correct 476 ms 24188 KB Output is correct