제출 #623573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
623573		MinaRagy06	Network (BOI15_net)	C++17	18 / 100	8 ms	12264 KiB

net

#include <bits/stdc++.h>
using namespace std;
#define lesgooo ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl    '\n'
#define int     long long
 
vector<int> adj[500'005];
int dist[500'005];
void dfs(int i, int sum, int par)
{
    dist[i] = sum;
    for (auto nxt : adj[i]) if (nxt != par) dfs(nxt, sum+1, i);
}
signed main()
{
    lesgooo;
    int n, u, v, sz = 0;
    cin >> n;
    for (int i = 0; i < n-1; i++) cin >> u >> v, adj[--v].push_back(--u), adj[u].push_back(v);
    int st;
    for (int i = 0; i < n; i++) if (adj[i].size() == 1) st = i;
    dfs(st, 0, -1);
    vector<pair<int, int>> a;
    for (int i = 0; i < n; i++) if (adj[i].size() == 1) sz++, a.push_back({dist[i], i});
    sort(a.begin(), a.end());
    int l = 0, r = a.size()-1;
    cout << (sz+1)/2 << endl;
    while (l < r) cout << a[l++].second+1 << " " << a[r--].second+1 << endl;
    if (l == r)
    {
        int mx = 0, x = 0;
        dfs(a[l].second, 0, -1);
        for (int i = 0; i < n; i++) if (i != l && dist[i] >= mx) mx = dist[i], x =i;
        cout << a[l].second+1 << " " << x+1 << endl;
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

net.cpp: In function 'int main()':
net.cpp:22:8: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
   22 |     dfs(st, 0, -1);
      |     ~~~^~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 0 / 45
• Subtask 3: 0 / 37