Submission #715787

#	Time	Username	Problem	Language	Result	Execution time	Memory
715787		Charizard2021	Network (BOI15_net)	C++17	63 / 100	2051 ms	77956 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];
int n;
int ans = 0;
int cur_ans = 0;
int subtreeValue = 0;
vector<int> arrVectors[N];
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;
}
bool cmp(const int &a, const int &b){
    if(arrVectors[a].size() == arrVectors[b].size()){
        if(arrVectors[a].empty()){
            return true;
        }
        return arrVectors[a][0] > arrVectors[b][0];
    }
    return arrVectors[a].size() > arrVectors[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";
    int x12 = cut(n);
    int idx = 0;
    vector<int> finalAns(2 * ans);
    set<int, bool (*)(const int&, const int&)> s(cmp);
    for(int i = 1; i <= subtreeValue; i++){
        for(int j = 0; j < res[i].size(); j++){
            arrVectors[i].push_back(res[i][j]);
        }
    }
    for(int i = 1; i <= subtreeValue; i++){
        s.insert(i);
    }
    while(true){
        int a = *(s.begin());
        auto it = s.begin();
        it++;
        int b = *(it);
        if(arrVectors[a].size() == 0 && arrVectors[b].size() == 0){
            break;
        }
        else if(arrVectors[b].size() == 0){
            finalAns[idx] = arrVectors[a][0];
            idx++;
            s.erase(a);
            arrVectors[a].erase(arrVectors[a].begin());
            s.insert(a);
        }
        else{
            finalAns[idx] = arrVectors[a][0];
            finalAns[idx + 1] = arrVectors[b][0];
            idx += 2;
            s.erase(a);
            arrVectors[a].erase(arrVectors[a].begin());
            s.insert(a);
            s.erase(b);
            arrVectors[b].erase(arrVectors[b].begin());
            s.insert(b);
        }
    }
    if(!(finalAns.empty()) && finalAns.back() == 0){
        finalAns.back() = x12;
    }
    for(int i = 0; i < (int)finalAns.size(); i += 2){
        cout << finalAns[i] << " " << finalAns[i + 1] << "\n";
    }
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int j = 0; j < res[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~

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