oj.uz

Submission #911479

# Submission time Handle Problem Language Result Execution time Memory
911479 2024-01-19T01:57:27 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;

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});
    cout<<(n+1)/2<<'\n';
    while (!pq.empty())
    {
        if (pq.size()>1)
        {
            auto f=pq.top().second;
            pq.pop();
            auto s=pq.top().second;
            pq.pop();
            cout<<l[f][l[f].size()-1]<<' '<<l[s][l[s].size()-1]<<'\n';
            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;
            cout<<1+(l[f][0]==1)<<' '<<l[f][0]<<'\n';
            pq.pop();
        }
    }

}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 25180 KB Invalid number of links.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 25180 KB Invalid number of links.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 25180 KB Invalid number of links.
2 Halted 0 ms 0 KB -