oj.uz

Submission #630401

# Submission time Handle Problem Language Result Execution time Memory
630401 2022-08-16T10:16:45 Z MasterTaster Network (BOI15_net) C++14
0 / 100
 4 ms 4992 KB 
#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define MAXN 200010

using namespace std;

int n;
vector<int> g[MAXN], listovi;
bool bio[MAXN];

void dfs(int u)
{
    bio[u]=true;
    if (g[u].size()==1) listovi.pb(u);
    for (auto v:g[u]) if (!bio[v]) dfs(v);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>>n;
    if (n==1) { cout<<1<<endl<<1<<" "<<1; exit(0); }
    if (n==2) { cout<<1<<endl<<1<<" "<<2; exit(0); }

    for (int i=1; i<n; i++)
    {
        int u, v; cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }

    for (int i=1; i<n; i++) if (g[i].size()!=1) { dfs(i); break; }

    //for (int i=0; i<listovi.size(); i++) cout<<listovi[i]<<" ";

    cout<<(listovi.size()+1)/2<<endl;
    for (int i=0; i<listovi.size()/2; i++)
    {
        cout<<listovi[i]<<" "<<listovi[i+listovi.size()/2]<<endl;
    }
    if (listovi.size()%2) cout<<listovi[listovi.size()-2]<<" "<<listovi[listovi.size()-1];
}

Compilation message

net.cpp: In function 'int main()':
net.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i=0; i<listovi.size()/2; i++)
      |                   ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Incorrect 3 ms 4992 KB Invalid number of links.
6 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Incorrect 3 ms 4992 KB Invalid number of links.
6 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Incorrect 3 ms 4992 KB Invalid number of links.
6 Halted 0 ms 0 KB -