Submission #717342

#	Time	Username	Problem	Language	Result	Execution time	Memory
717342		Charizard2021	Network (BOI15_net)	C++17	0 / 100	18 ms	35540 KiB

net

#include<bits/stdc++.h>
using namespace std;
const int N = 500001;
#define IOS ios::sync_with_stdio(false);; cin.tie(NULL)
bool visited[N];
int LeavesInsubtee[N];
vector<int> adj[N];
vector<int> res[N];
vector<int> v2[N];
int n;
int ans = 0;
int cur_ans = 0;
int subtreeValue = 0;
void dfs(int u){
    visited[u] = true;
    if((int)adj[u].size() == 1){
        LeavesInsubtee[u] = 1;
    }
    for(int v : adj[u]){
        if(!visited[v]){
            dfs(v);
            LeavesInsubtee[u] += LeavesInsubtee[v];
        }
    }
}
void dfs2(int u){
    visited[u] = true;
    if((int)adj[u].size() == 1){
        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((cur_ans)/2)){
                return cutlocation(v);
            }
        }
    }
    return u;
}
int cut(int u){
    dfs(1);
    for(int i = 1; i <= n; i++){
        visited[i] = false;
    }
    int x = cutlocation(1);
    for(int i = 1; i <= n; i++){
        visited[i] = false;
    }
    visited[x] = true;
    for(int v : adj[x]){
        subtreeValue++;
        dfs2(v);
    }
    return x;
}
struct cmp{
    bool operator()(const int &a, const int &b) const{
        if(res[a].size() == res[b].size()){
            return a < b;
        }
        return res[a].size() > res[b].size();
    }
};
int main(){
    IOS;
    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++;
        }
    }
    cur_ans = ans;
    ans = (ans + 1)/2;
    cout << ans << "\n";
    cut(n);
    vector<int> v;
    int num = res[1][0];
    for(int i = 1; i <= subtreeValue; i++){
        v2[res[i].size()].push_back(i);
    }
    int first_pointer = -1;
    int second_pointer = -1;
    for(int i = N - 1; i > 0; i--){
        if(!v2[i].empty() && first_pointer == -1){
            first_pointer = i;
        }
        if(!v2[i].empty() && first_pointer != -1 && second_pointer == -1){
            second_pointer = i;
        }
    }
    while(first_pointer != 0){
        int x = v2[first_pointer].back();
        v.push_back(res[x].back());
        v2[first_pointer].pop_back();
        res[x].pop_back();
        if(second_pointer != -1 && v2[second_pointer].size() != 0){
            int y = v2[second_pointer].back();
            v.push_back(res[y].back());
            v2[second_pointer].pop_back();
            res[y].pop_back();
            if(!res[y].empty()){
                v2[res[y].size()].push_back(y);
            }
            if(v2[res[y].size() + 1].size() == 0){
                second_pointer--;
            }
        }
        if(!res[x].empty()){
            v2[res[x].size()].push_back(x);
        }
        if(v2[res[x].size() + 1].size() == 0){
            first_pointer--;
        }
    }
    if(v.size() % 2 == 1){
        v.push_back(num);
    }
    for(int i = 0; i < (int)v.size(); i += 2){
        cout << v[i] << " " << v[i + 1] << "\n";
    }
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 45
• Subtask 3: 0 / 37