oj.uz

Submission #96086

# Submission time Handle Problem Language Result Execution time Memory
96086 2019-02-05T17:15:49 Z andrei110901 Network (BOI15_net) C++14
0 / 100
 6 ms 504 KB 
#include <bits/stdc++.h>

using namespace std;

vector <vector <int>> ad;
vector <int> sub;
vector <bool> viz;
int nrf, cf;

void dfs(int nod){
    viz[nod] = true;
    for(auto fiu : ad[nod])
        if(!viz[fiu]){
            dfs(fiu);
            sub[nod] += sub[fiu];
        }
    if(ad[nod].size() == 1)
        sub[nod] = 1;
    if(cf == 0 && 2 * sub[nod] >= nrf && ad[nod].size() != 1)
        cf = nod;
}

bool cmp(const vector <int> &a, const vector <int> &b){
    return a.size() > b.size();
}

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

int main()
{
    int n, x, y;
    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);
        if(ad[x].size() == 2)
            nrf--;
        if(ad[y].size() == 2)
            nrf--;
    }
    viz.resize(n + 1);
    dfs(1);
    fill(viz.begin(), viz.end(), false);
    viz[cf] = true;
    vector <vector <int>> gramezi;
    for(auto fiu : ad[cf]){
        vector <int> v;
        gramezi.push_back(v);
        Frunza(fiu, gramezi.back());
    }
    cout << (nrf + 1) / 2 << '\n';
    if(nrf % 2 == 1){
        cout << cf << ' ' << gramezi[0].back() << '\n';
        gramezi[0].pop_back();
        sort(gramezi.begin(), gramezi.end(), cmp);
    }
    while(gramezi[0].size() > 0){
        cout << gramezi[0].back() << ' ' << gramezi[1].back() << '\n';
        gramezi[0].pop_back();
        gramezi[1].pop_back();
        sort(gramezi.begin(), gramezi.end(), cmp);
    }
    return 0;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 252 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Runtime error 6 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 252 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Runtime error 6 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 252 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Runtime error 6 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -