제출 #1189052

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1189052		pxsit	Network (BOI15_net)	C++20	18 / 100	221 ms	14248 KiB

net

#include <bits/stdc++.h>
using namespace std;
int n,m,k,q;
vector<int> adj[(int)5e5+5];
vector<int> depth((int)5e5+5);
vector<pair<int,int>> v;
void dfs(int x, int i){
    if(adj[x].size() == 1){
        v.emplace_back(depth[x], x);
        return;
    }
    for(auto xx:adj[x]){
        if(xx == i) continue;
        depth[xx] = depth[x] + 1;
        dfs(xx, x);
    }
}
int main(){
    cin >> n;
    for(int i = 2; i <= n; i++){
        int a,b;
        cin >> a >> b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }
    vector<pair<int,int>> u;
    int sz = INT_MAX;
    for(int i = 1; i <= n; i++){
        vector<pair<int,int>> ans;
        vector<int> op;
        for(auto x : adj[i]){
            depth[x] = 1;
            v.clear();
            dfs(x, i);
            sort(v.begin(), v.end(), greater<pair<int,int>>());
            ans.emplace_back(i, v[0].second);
            for(int j = 2; j < v.size(); j += 2)
                ans.emplace_back(v[j-1].second, v[j].second);
            if(v.size() % 2 == 0)
                op.push_back(v.back().second);
        }
        for(int k = 1; k < op.size(); k += 2)
            ans.emplace_back(op[k-1], op[k]);
        if(op.size() % 2 == 1)
            ans.emplace_back(op.back(), i);
        if(sz > ans.size()){
            u = ans;
            sz = ans.size();
        }
    }
    cout << u.size() << '\n';
    for(auto [a, b] : u){
        cout << a << ' ' << b << '\n';
    }
}

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