oj.uz

답안 #630405

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
630405 2022-08-16T10:27:34 Z MasterTaster Network (BOI15_net) C++14
0 / 100
 6 ms 11988 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 500010
 
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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Incorrect 6 ms 11988 KB Invalid number of links.
6 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Incorrect 6 ms 11988 KB Invalid number of links.
6 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Incorrect 6 ms 11988 KB Invalid number of links.
6 Halted 0 ms 0 KB -