oj.uz

Submission #580239

# Submission time Handle Problem Language Result Execution time Memory
580239 2022-06-20T19:16:34 Z Omar_Elgedawy Network (BOI15_net) C++14
0 / 100
 15 ms 23796 KB 
#include <bits/stdc++.h>
using namespace std;
#define cin(vec)        for(auto& i : vec) cin >> i
#define cout(vec)       for(auto& i : vec) cout << i << " "; cout << "\n";
#define fast            ios::sync_with_stdio(0);cin.tie(0);
#define loop(i,a,b)     for (int i = a; i < b; i++)
#define F               first
#define S               second
#define pb(n)           push_back(n)
#define pf(n)           push_front(n)
#define dci(d)          fixed<<setprecision(d)
#define sp              ' '
#define el              '\n'
#define all(v)          v.begin(),v.end()
#define int             long long
int dx[8]= {0,0,1,-1,-1,1,1,-1};
int dy[8]= {-1,1,0,0,-1,1,-1,1};
int const N=5e5+5,M=1e3+1,Mod=1e9+7;
vector<int>adj[N],par[N];
int n,dep[N];
void testcase(int h){
  cin>>n;
  for(int i=0;i<n-1;i++){
    int u,v;cin>>u>>v;
    adj[u].pb(v);
    adj[v].pb(u);
    dep[u]++;
    dep[v]++;
  }
  deque<pair<int,int>>ans;
  vector<pair<int,int>>leaf;
  for(int i=1;i<=n;i++){
    if(dep[i]==1){
      leaf.push_back({adj[i][0],i});
    }
  }
  sort(all(leaf));
  int sz=leaf.size();
  if(sz%2){
    cout<<sz/2+1<<el;
    for(int i=0;i<sz/2;i++){
      cout<<leaf[i].S<<' '<<leaf[i+sz/2+1].S<<el;
    }
    cout<<leaf[sz/2].S<<' '<<2<<el;
  }
  else{
    cout<<sz/2<<el;
    for(int i=0;i<sz/2;i++){
      cout<<leaf[i].S<<' '<<leaf[i+sz/2].S<<el;
    }
  }
}
int32_t main()
{
  // fast
  testcase(1);
  // int tc;cin>>tc;for(int i=1;i<=tc;i++)testcase(i);
  return 0;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23668 KB Output is correct
2 Correct 13 ms 23676 KB Output is correct
3 Correct 13 ms 23752 KB Output is correct
4 Correct 13 ms 23724 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 12 ms 23700 KB Output is correct
8 Correct 12 ms 23796 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 15 ms 23728 KB Output is correct
11 Correct 14 ms 23788 KB Output is correct
12 Correct 13 ms 23776 KB Output is correct
13 Correct 13 ms 23796 KB Output is correct
14 Correct 12 ms 23764 KB Output is correct
15 Correct 12 ms 23700 KB Output is correct
16 Incorrect 12 ms 23764 KB Breaking single line is causing network to disconnect.
17 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23668 KB Output is correct
2 Correct 13 ms 23676 KB Output is correct
3 Correct 13 ms 23752 KB Output is correct
4 Correct 13 ms 23724 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 12 ms 23700 KB Output is correct
8 Correct 12 ms 23796 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 15 ms 23728 KB Output is correct
11 Correct 14 ms 23788 KB Output is correct
12 Correct 13 ms 23776 KB Output is correct
13 Correct 13 ms 23796 KB Output is correct
14 Correct 12 ms 23764 KB Output is correct
15 Correct 12 ms 23700 KB Output is correct
16 Incorrect 12 ms 23764 KB Breaking single line is causing network to disconnect.
17 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23668 KB Output is correct
2 Correct 13 ms 23676 KB Output is correct
3 Correct 13 ms 23752 KB Output is correct
4 Correct 13 ms 23724 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 12 ms 23700 KB Output is correct
8 Correct 12 ms 23796 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 15 ms 23728 KB Output is correct
11 Correct 14 ms 23788 KB Output is correct
12 Correct 13 ms 23776 KB Output is correct
13 Correct 13 ms 23796 KB Output is correct
14 Correct 12 ms 23764 KB Output is correct
15 Correct 12 ms 23700 KB Output is correct
16 Incorrect 12 ms 23764 KB Breaking single line is causing network to disconnect.
17 Halted 0 ms 0 KB -