oj.uz

Submission #310014

# Submission time Handle Problem Language Result Execution time Memory
310014 2020-10-05T10:23:06 Z nicolaalexandra Network (BOI15_net) C++14
0 / 100
 9 ms 12160 KB 
#include <bits/stdc++.h>
#define DIM 500010
using namespace std;

vector <int> L[DIM],v;
int g[DIM];
int n,i,j,x,y,rad;

void dfs (int nod, int tata){
    int ok = 0;
    for (auto vecin : L[nod])
        if (vecin != tata){
            ok = 1;
            dfs (vecin,nod);
        }
    if (!ok)
        v.push_back(nod);
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<n;i++){
        cin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
        g[x]++, g[y]++;
    }

    for (i=1;i<=n;i++)
        if (g[i] >= 2){
            rad = i;
            break;
        }

    dfs (rad,0);

    cout<<(v.size()+1)/2<<"\n";

    if (v.size() % 2){
        cout<<v.back()<<" "<<rad<<"\n";
        v.pop_back();
    }

    i = 0, j = v.size()-1;
    while (i < j){
        cout<<v[i]<<" "<<v[j]<<"\n";
        i++, j--;
    }

    return 0;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12160 KB Output is correct
2 Incorrect 9 ms 12160 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12160 KB Output is correct
2 Incorrect 9 ms 12160 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12160 KB Output is correct
2 Incorrect 9 ms 12160 KB Breaking single line is causing network to disconnect.
3 Halted 0 ms 0 KB -