Submission #710821

#	Time	Username	Problem	Language	Result	Execution time	Memory
710821		noedit	Network (BOI15_net)	C++17	100 / 100	643 ms	65612 KiB

net

#include <bits/stdc++.h>
#include <quadmath.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#define sz(x) (int)x.size()
//#define sqr(x) x*x
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("fast-math")
using namespace std;
//using namespace __gnu_pbds;
//
//#define int long long
////#define ld long double
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;

vector<vector<int> > g;

vector<int> pr;
vector<int> tin, tout;
vector<int> ls;
vector<int> ord;
vector<int> tin_ord;

int timer = 0;

void dfs(int v, int p)
{
    tin[v] = timer++;
    pr[v] = p;
    if (g[v].size() == 1){
        ls[v]++;
        tin_ord.push_back(tin[v]);
        ord.push_back(v);
    }
    for (auto&u : g[v])
    {
        if (u != p)
        {
            dfs(u, v);
            ls[v] += ls[u];
        }
    }
    tout[v] = timer++;
}

int root = 0;

int cock(int v, int p)
{
    for (auto& u : g[v])
    {
        if (u != p)
        {
            if (ls[u] > ls[root] / 2)
            {
                return cock(u, v);
            }
        }
    }
    return v;
}

void solve()
{
    int n;
    cin >> n;
    g.resize(n);
    pr.resize(n);
    ls.resize(n);
    tin.resize(n);
    tout.resize(n);
    for (int i = 0; i < n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    for (int i = 0; i < n; i++)
        if (g[i].size() > 1)
        root = i;
    dfs(root, root);
    vector<int> ans(ls[root] + ls[root] % 2);
    vector<int> cur;
    int j = cock(root, root);
    int lt = lower_bound(tin_ord.begin(), tin_ord.end(), tin[j]) - tin_ord.begin();
    int rt = upper_bound(tin_ord.begin(), tin_ord.end(), tout[j]) - tin_ord.begin() - 1;
    int k = 0;
    int fist = -1;
    for (int i = 0; i < lt; i++)
    {
        ans[k] = ord[i];
        if (fist == -1) fist = ord[i];
        k += 2;
        if (k == ans.size()) k = 1;
    }
    for (int i = rt + 1; i < ord.size(); i++)
    {
        ans[k] = ord[i];
        if (fist == -1) fist = ord[i];
        k += 2;
        if (k == ans.size()) k = 1;
    }
    for (auto& u : g[j])
    {
        if (u != pr[j])
        {
            int l = lower_bound(tin_ord.begin(), tin_ord.end(), tin[u]) - tin_ord.begin();
            int r = upper_bound(tin_ord.begin(), tin_ord.end(), tout[u]) - tin_ord.begin() - 1;
            for (int i = l; i <= r; i++)
            {
                 ans[k] = ord[i];
        if (fist == -1) fist = ord[i];
                 k += 2;
                 if (k == ans.size()) k = 1;
            }
        }
    }
    if (ls[root] % 2 == 1)
    {
        ans[ans.size() - 1] = fist;
    }
    cout << ans.size() / 2 << endl;
    for (int i = 0; i < ans.size(); i += 2)
    {
        cout << ans[i] + 1 << ' ' << ans[i + 1] + 1 << endl;
    }
}
//
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    cerr << endl << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
    return 0;
}
//
//
/*
17 13
1 3 1 2 1 3 1 2 1 1 2 1 2 1 2 1 3
3 1 2 3 3 2 1 2 1 3 2 2 1
*/
/*
6 9
3 2 1 6 7 4
3 2 6 10 8 9 7 1 4
*/
/*
9 8
2 1 4 6 7 8 9 10 11
8 9 10 11 1 4 6 7
*/

Compilation message (stderr)

net.cpp: In function 'void solve()':
net.cpp:102:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         if (k == ans.size()) k = 1;
      |             ~~^~~~~~~~~~~~~
net.cpp:104:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for (int i = rt + 1; i < ord.size(); i++)
      |                          ~~^~~~~~~~~~~~
net.cpp:109:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         if (k == ans.size()) k = 1;
      |             ~~^~~~~~~~~~~~~
net.cpp:122:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |                  if (k == ans.size()) k = 1;
      |                      ~~^~~~~~~~~~~~~
net.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for (int i = 0; i < ans.size(); i += 2)
      |                     ~~^~~~~~~~~~~~

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