Submission #941040

#	Time	Username	Problem	Language	Result	Execution time	Memory
941040		darya_navard	Network (BOI15_net)	C++17	100 / 100	548 ms	77264 KiB

net

#include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;

int n, sz[N];
vector<int> adj[N];

int dfssz(int u, int p = 0){
    sz[u] = (adj[u].size() < 2);
    for (auto v : adj[u])
        if (v ^ p) sz[u] += dfssz(v, u);
    return sz[u];
}
 
int centroid(int u, int cnt, int p = 0){
    for (auto v : adj[u])
        if(v ^ p && sz[v] > cnt / 2) return centroid(v, cnt, u);
    return u;
}
 
void dfs(int u, int p, vector<int> &comp){
    if (adj[u].size() == 1) comp.emplace_back(u);
    for (auto v : adj[u])
        if(v ^ p) dfs(v,u,comp);
}
 
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u,v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    int c = centroid(1, dfssz(1));
    vector<vector<int>> res;
    for(auto v:adj[c]) {
        res.push_back({});
        dfs(v,c,res.back());
    }
    priority_queue<pair<int,int>> pq;
    for (int i = 0; i < res.size(); i++) pq.emplace(res[i].size(),i);
    vector<pair<int,int>> ans;
    while (!pq.empty()) {
        auto [s,i]=pq.top();
        pq.pop();
        if (pq.empty()){
            ans.emplace_back(res[i].back(),c);
            break;
        }
        auto [t,j] = pq.top();
        pq.pop();
        ans.emplace_back(res[i].back(),res[j].back());
        res[i].pop_back();
        res[j].pop_back();
        if(--s) pq.emplace(s,i);
        if(--t) pq.emplace(t,j);
    }
    cout << ans.size() << endl;
    for(auto [x,y] : ans) cout << x << " " << y << endl;
}

Compilation message (stderr)

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

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