Submission #1094897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094897		andrei_iorgulescu	Village (BOI20_village)	C++14	100 / 100	75 ms	27784 KiB

Village

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n;
vector<int> g[100005], f[100005];
int t[100005], sz[100005], h[100005];
int nrf[100005];

int ans_mic, ans_mare, sol_mic[100005], sol_mare[100005];

void dfs(int nod)
{
    sz[nod] = 1;
    for (auto vecin : g[nod])
    {
        if (vecin != t[nod])
        {
            f[nod].push_back(vecin);
            t[vecin] = nod;
            h[vecin] = 1 + h[nod];
            dfs(vecin);
            sz[nod] += sz[vecin];
        }
    }
}

void solve_mic()
{
    vector<bool> scos(n + 1);
    for (int i = 1; i <= n; i++)
        nrf[i] = f[i].size();
    vector<int> nd;
    for (int i = 1; i <= n; i++)
        nd.push_back(i);
    sort(nd.begin(), nd.end(), [](int A, int B)
    {
        return h[A] > h[B];
    });
    for (auto it : nd)
    {
        if (nrf[it] != 0)
        {
            vector<int> u;
            for (auto itt : f[it])
            {
                if (!scos[itt])
                {
                    scos[itt] = true;
                    u.push_back(itt);
                }
            }
            scos[it] = true;
            nrf[t[it]]--;
            if (u.size() % 2 == 1)
            {
                u.push_back(it);
                ans_mic -= 2;
                for (int i = 0; i < u.size(); i += 2)
                {
                    ans_mic += 4;
                    sol_mic[u[i]] = u[i + 1];
                    sol_mic[u[i + 1]] = u[i];
                }
            }
            else
            {
                int x = it, y = u[0], z = u[1];
                ans_mic += 4;
                sol_mic[x] = y;
                sol_mic[y] = z;
                sol_mic[z] = x;
                for (int i = 2; i < u.size(); i += 2)
                {
                    ans_mic += 4;
                    sol_mic[u[i]] = u[i + 1];
                    sol_mic[u[i + 1]] = u[i];
                }
            }
        }
        else if (it == 1)
        {
            ans_mic += 2;
            int x = f[1][0];
            int y = sol_mic[x];
            if (sol_mic[y] == x)
            {
                sol_mic[1] = x;
                sol_mic[x] = y;
                sol_mic[y] = 1;
            }
            else
            {
                int z = sol_mic[y];
                sol_mic[1] = x;
                sol_mic[x] = y;
                sol_mic[y] = z;
                sol_mic[z] = 1;
            }
        }
    }
}

int find_centroid(int nod)
{
    int ff = 0;
    for (auto it : f[nod])
        if (sz[it] > n / 2)
            ff = it;
    if (ff != 0)
        return find_centroid(ff);
    return nod;
}

vector<int> noduri;

void dfs2(int nod)
{
    noduri.push_back(nod);
    for (auto it : f[nod])
        dfs2(it);
}

void solve_mare()
{
    int c = find_centroid(1);
    for (int i = 1; i <= n; i++)
    {
        f[i].clear();
        t[i] = 0;
        sz[i] = 0;
        h[i] = 0;
    }
    dfs(c);
    for (int i = 1; i <= n; i++)
        ans_mare += 2 * h[i];
    dfs2(c);
    int ofs = (n + 1) / 2;
    for (int i = 0; i < noduri.size(); i++)
    {
        int x = (i + ofs) % n;
        sol_mare[noduri[i]] = noduri[x];
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1);
    solve_mic();
    solve_mare();
    cout << ans_mic << ' ' << ans_mare << '\n';
    for (int i = 1; i <= n; i++)
        cout << sol_mic[i] << ' ';
    cout << '\n';
    for (int i = 1; i <= n; i++)
        cout << sol_mare[i] << ' ';
    return 0;
}

Compilation message (stderr)

Village.cpp: In function 'void solve_mic()':
Village.cpp:61:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |                 for (int i = 0; i < u.size(); i += 2)
      |                                 ~~^~~~~~~~~~
Village.cpp:75:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |                 for (int i = 2; i < u.size(); i += 2)
      |                                 ~~^~~~~~~~~~
Village.cpp: In function 'void solve_mare()':
Village.cpp:141:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |     for (int i = 0; i < noduri.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 38 / 38
• Subtask 3: 50 / 50