oj.uz

Submission #221990

# Submission time Handle Problem Language Result Execution time Memory
221990 2020-04-11T16:37:29 Z mohamedsobhi777 Network (BOI15_net) C++14
0 / 100
 7 ms 4992 KB 
#include<bits/stdc++.h>

using namespace std ; 
const int N = 2e5 + 7 ; 

int n; 
map<pair<int , int> , bool > is ; 

vector<int> adj[N] ; 
int node , dist ; 
bool vis[N] ;

int dfs(int x , int p , int h){
    
    for(auto u : adj[x]){
        if(u==p)continue ; 
        dfs(u , x , h+1 ) ; 
    }
    if(!vis[x] && adj[x].size() == 1){
        if(h > dist){
            dist = h ; 
            node = x ; 
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0) ; 
    cin.tie(0) ; 
    //freopen("in.in" , "r" , stdin) ;    
    cin>>n ; 
    for(int i = 0 ; i < n- 1 ; i++){
        int a , b ; 
        cin>>a>>b ; 
        if(a > b)swap(a , b) ; 
        adj[a].push_back(b) ; 
        adj[b].push_back(a) ; 
        is[{a , b}] = 1; 
    }
    int k = 0 ; 
    for(int i = 1 ;i<=n ;i++){
        k+=(adj[i].size()==1) ; 
    }
    cout<<(k+1)/2<<'\n' ; 
    while(k > 1){
        dist = node = 0; 
        dfs(1 , 1 , 0) ; 
        int L = node ; 
        dist = node = 0; 
        dfs(L , L , 0) ; 
        cout<<node<<' ' << L<<'\n' ; 
        vis[L] = vis[node] = 1 ;
        k-=2 ; 
    }
    if(k){
        for(int i = 1 ;i <=n;i++){
            if(adj[i].size() > 1 || vis[i])continue ; 
            for(int j = 1 ; j<=n;j++){
                if(j==i)continue ; 
                int a = min(i , j) , b = max(i , j) ; 
                if(is[{a , b}])continue ; 
                cout<<a<<' ' <<b; 
                return 0; 
            }
        }
    }
    return 0 ; 
}

Compilation message

net.cpp: In function 'int dfs(int, int, int)':
net.cpp:25:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Incorrect 7 ms 4992 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Incorrect 7 ms 4992 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Incorrect 7 ms 4992 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -