Submission #96093

#	Time	Username	Problem	Language	Result	Execution time	Memory
96093		andrei110901	Network (BOI15_net)	C++14	100 / 100	1046 ms	92636 KiB

net

#include <bits/stdc++.h>

using namespace std;

vector <vector <int>> ad, gramezi;
vector <int> sub;
int nrf, cf;

void dfs(int nod, int par){
    if(ad[nod].size() == 1)
        sub[nod] = 1;
    for(auto fiu : ad[nod])
        if(fiu != par){
            dfs(fiu, nod);
            sub[nod] += sub[fiu];
        }
}

int get_centroid(int nod, int par){
    for(auto fiu : ad[nod])
        if(fiu != par && sub[fiu] > nrf / 2)
            return get_centroid(fiu, nod);
    return nod;
}

struct cmp{
    bool operator()(const int &lhs, const int &rhs){
        if(gramezi[lhs].size() == gramezi[rhs].size())
            return lhs < rhs;
        return gramezi[lhs].size() > gramezi[rhs].size();
    }
};


void Frunza(int nod, int par, vector <int> &v){
    if(ad[nod].size() == 1){
        v.push_back(nod);
        return;
    }
    for(auto fiu : ad[nod])
        if(fiu != par)
            Frunza(fiu, nod, v);
}

int main()
{
    int n, x, y;
    //ios::sync_with_stdio(false);
    cin >> n;
    nrf = n;
    ad.resize(n + 1);
    sub.resize(n + 1);
    for(int i = 1; i < n; i++){
        cin >> x >> y;
        ad[x].push_back(y);
        ad[y].push_back(x);
    }
    dfs(1, 0);
    nrf = sub[1];
    cf = get_centroid(1, 0);
    set <int, cmp> q;
    for(auto fiu : ad[cf]){
        vector <int> v;
        Frunza(fiu, cf, v);
        gramezi.push_back(v);
    }
    for(int i = 0; i < gramezi.size(); i++)
        q.insert(i);
    cout << (nrf + 1) / 2 << '\n';
    if(nrf % 2 == 1){
        int aux = *q.begin();
        q.erase(q.begin());
        cout << cf << ' ' << gramezi[aux].back() << '\n';
        gramezi[aux].pop_back();
        q.insert(aux);
    }
    while(gramezi[*(q.begin())].size() > 0){
        int i1 = *(q.begin());
        q.erase(q.begin());
        int i2 = *(q.begin());
        q.erase(q.begin());
        cout << gramezi[i1].back() << ' ' << gramezi[i2].back() << '\n';
        gramezi[i1].pop_back();
        gramezi[i2].pop_back();
        q.insert(i1);
        q.insert(i2);
    }
    return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:67:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < gramezi.size(); i++)
                    ~~^~~~~~~~~~~~~~~~

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