oj.uz

답안 #911480

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
911480 2024-01-19T01:59:04 Z 12345678 Network (BOI15_net) C++17
0 / 100
 7 ms 25180 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;
int n, u, v, st, sz[nx], c, res;
vector<int> d[nx], l[nx];
priority_queue<pair<int, int>> pq;
vector<pair<int, int>> ans;

int dfssz(int u, int p)
{
    sz[u]=(d[u].size()==1);
    for (auto v:d[u]) if (v!=p) sz[u]+=dfssz(v, u);
    return sz[u];
}

int findcentroid(int u, int p, int rtsz)
{
    for (auto v:d[u]) if (v!=p&&sz[v]*2>rtsz) return findcentroid(v, u, rtsz);
    return u;
}

void dfsadd(int u, int p, vector<int> &x)
{
    if (d[u].size()==1) x.push_back(u);
    for (auto v:d[u]) if (v!=p) dfsadd(v, u, x); 
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=0; i<n-1; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
    for (int i=0; i<n; i++) if (d[i].size()>1) st=i;
    c=findcentroid(st, st, dfssz(st, st));
    for (auto v:d[c]) dfsadd(v, c, l[v]);
    for (auto v:d[c]) pq.push({l[v].size(), v});
    while (!pq.empty())
    {
        if (pq.size()>1)
        {
            auto f=pq.top().second;
            pq.pop();
            auto s=pq.top().second;
            pq.pop();
            ans.push_back({l[f][l[f].size()-1], l[s][l[s].size()-1]});
            l[f].pop_back(); l[s].pop_back();
            if (!l[f].empty()) pq.push({l[f].size(), f});
            if (!l[s].empty()) pq.push({l[s].size(), s});
        }
        else 
        {
            auto f=pq.top().second;
            ans.push_back({1+(l[f][0]==1), l[f][0]});
            pq.pop();
        }
    }
    cout<<ans.size()<<'\n';
    for (auto [x, y]:ans) cout<<x<<' '<<y<<'\n';
}

Subtask #1
0 / 18.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 37.0

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