oj.uz

Submission #270503

# Submission time Handle Problem Language Result Execution time Memory
270503 2020-08-17T16:48:38 Z Hehehe Network (BOI15_net) C++14
0 / 100
 33 ms 47360 KB 
#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define sz(x) (int)((x).size())
//#define int long long

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const ll inf = 2e9;
const ll mod = 1e9 + 7;
const int N = 2e6 + 11;
const ll INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);

//ifstream in(".in");
//ofstream out(".out");

int n, m;
vector<int>v[N];

void solve(){

    cin >> n;

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

    int root = 0;
    vector<int>leaves;
    for(int i = 1; i <= n; i++){
        if(sz(v[i]) == 1){
            leaves.push_back(i);
        }
        if(sz(v[i]) > 1)root = i;
    }

    int ans = sz(leaves)/2 + sz(leaves) % 2;

    cout << ans << '\n';

    for(int i = 0; i < ans; i ++){
        cout << leaves[i] << ' ' << leaves[i + sz(leaves)/2] << '\n';
    }
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
}

Compilation message

net.cpp: In function 'void solve()':
net.cpp:39:9: warning: variable 'root' set but not used [-Wunused-but-set-variable]
   39 |     int root = 0;
      |         ^~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47232 KB Output is correct
2 Correct 31 ms 47224 KB Output is correct
3 Correct 32 ms 47232 KB Output is correct
4 Correct 31 ms 47228 KB Output is correct
5 Correct 32 ms 47360 KB Output is correct
6 Correct 31 ms 47232 KB Output is correct
7 Correct 33 ms 47224 KB Output is correct
8 Correct 31 ms 47232 KB Output is correct
9 Correct 31 ms 47232 KB Output is correct
10 Correct 33 ms 47348 KB Output is correct
11 Correct 31 ms 47224 KB Output is correct
12 Incorrect 32 ms 47232 KB Breaking single line is causing network to disconnect.
13 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47232 KB Output is correct
2 Correct 31 ms 47224 KB Output is correct
3 Correct 32 ms 47232 KB Output is correct
4 Correct 31 ms 47228 KB Output is correct
5 Correct 32 ms 47360 KB Output is correct
6 Correct 31 ms 47232 KB Output is correct
7 Correct 33 ms 47224 KB Output is correct
8 Correct 31 ms 47232 KB Output is correct
9 Correct 31 ms 47232 KB Output is correct
10 Correct 33 ms 47348 KB Output is correct
11 Correct 31 ms 47224 KB Output is correct
12 Incorrect 32 ms 47232 KB Breaking single line is causing network to disconnect.
13 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47232 KB Output is correct
2 Correct 31 ms 47224 KB Output is correct
3 Correct 32 ms 47232 KB Output is correct
4 Correct 31 ms 47228 KB Output is correct
5 Correct 32 ms 47360 KB Output is correct
6 Correct 31 ms 47232 KB Output is correct
7 Correct 33 ms 47224 KB Output is correct
8 Correct 31 ms 47232 KB Output is correct
9 Correct 31 ms 47232 KB Output is correct
10 Correct 33 ms 47348 KB Output is correct
11 Correct 31 ms 47224 KB Output is correct
12 Incorrect 32 ms 47232 KB Breaking single line is causing network to disconnect.
13 Halted 0 ms 0 KB -