oj.uz

Submission #710858

# Submission time Handle Problem Language Result Execution time Memory
710858 2023-03-16T02:41:42 Z Charizard2021 Network (BOI15_net) C++17
0 / 100
 13 ms 24276 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 500001;
bool isLeaf[N];
bool visited[N];
int LeavesInsubtee[N];
vector<int> adj[N];
vector<int> res[N];
int ans = 0;
int subtreeValue = 0;
void dfs(int u){
    visited[u] = true;
    LeavesInsubtee[u] = isLeaf[u];
    for(int v : adj[u]){
        if(!visited[v]){
            dfs(v);
            LeavesInsubtee[u] += LeavesInsubtee[v];
        }
    }
}
void dfs2(int u){
    visited[u] = true;
    if(isLeaf[u]){
        res[subtreeValue].push_back(u);
    }
    for(int v : adj[u]){
        if(!visited[v]){
            dfs2(v);
        }
    }
}
int cutlocation(int u){
    visited[u] = true;
    for(int v : adj[u]){
        if(!visited[v]){
            if(LeavesInsubtee[v] > floor(ans/2)){
                return cutlocation(v);
            }
        }
    }
    return u;
}
int cut(int u){
    dfs(1);
    memset(visited, false, sizeof(visited));
    int x = cutlocation(1);
    memset(visited, false, sizeof(visited));
    visited[x] = true;
    for(int v : adj[x]){
        subtreeValue++;
        dfs2(v);
    }
    return x;
}
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i = 1; i <= n; i++){
        if((int)adj[i].size() == 1){
            ans++;
            isLeaf[i] = true;
        }
    }
    ans = (ans + 1)/2;
    cout << ans << "\n";
    cut(n);
    vector<int> finalAns(2 * ans);
    int idx = 0;
    for(int i = 1; i <= subtreeValue; i++){
        for(int j = 0; j < (int)res[i].size(); j++){
            finalAns[idx] = res[i][j];
            idx += 2;
            if(idx == 2 * ans){
                idx = 1;
            }
        }
    }
    if(finalAns.size() != 0 && finalAns.back() == 0){
        finalAns.back() = res[1][0];
    }
    for(int i = 0; i < (int)finalAns.size(); i += 2){
        cout << finalAns[i] << " " << finalAns[i + 1] << "\n";
    }
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 24276 KB Breaking single line is causing network to disconnect.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 24276 KB Breaking single line is causing network to disconnect.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 24276 KB Breaking single line is causing network to disconnect.
2 Halted 0 ms 0 KB -