Submission #1262418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262418		cpismylifeOwO	Fun Tour (APIO20_fun)	C++20	47 / 100	76 ms	15548 KiB

fun

#include <bits/stdc++.h>
#ifndef cpismylifeOwO
#include "fun.h"
#endif // cpismylifeOwO
using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;
const int MaxLog = 20;

#ifdef cpismylifeOwO
int ni;
vector<int> graph[MaxN];

void Inp()
{
    cin >> ni;
    for (int x = 1; x < ni; x++)
    {
        int u, v;
        cin >> u >> v;
        u++;
        v++;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
}

int par[MaxN];
int h[MaxN];
int sz[MaxN];

void PreDFS(int u, int p)
{
    sz[u] = 1;
    for (int x : graph[u])
    {
        if (x != p)
        {
            par[x] = u;
            h[x] = h[u] + 1;
            PreDFS(x, u);
            sz[u] += sz[x];
        }
    }
}

int BinLift[MaxLog][MaxN];

void Build()
{
    for (int x = 1; x <= ni; x++)
    {
        BinLift[0][x] = par[x];
    }
    for (int x = 1; x < MaxLog; x++)
    {
        for (int y = 1; y <= ni; y++)
        {
            BinLift[x][y] = BinLift[x - 1][BinLift[x - 1][y]];
        }
    }
}

int LCA(int u, int v)
{
    if (h[u] != h[v])
    {
        if (h[u] > h[v])
        {
            swap(u, v);
        }
        int k = h[v] - h[u];
        for (int x = 0; x < MaxLog; x++)
        {
            if (k & (1 << x))
            {
                v = BinLift[x][v];
            }
        }
    }
    if (u == v)
    {
        return v;
    }
    for (int x = MaxLog - 1; x >= 0; x--)
    {
        if (BinLift[x][u] != BinLift[x][v])
        {
            u = BinLift[x][u];
            v = BinLift[x][v];
        }
    }
    return par[u];
}

int hoursRequired(int u, int v)
{
    cout << "a ";
    u++;
    v++;
    cout << u << " " << v << " ";
    int lca = LCA(u, v);
    cout << h[u] + h[v] - 2 * h[lca] << "\n";
    return h[u] + h[v] - 2 * h[lca];
}

int attractionsBehind(int u, int v)
{
    cout << "b ";
    u++;
    v++;
    cout << u << " " << v << " ";
    int lca = LCA(u, v);
    if (lca == v)
    {
        for (int x = MaxLog - 1; x >= 0; x--)
        {
            if (h[u] - (1 << x) > h[v])
            {
                u = BinLift[x][u];
            }
        }
        cout << ni - sz[u] << "\n";
        return ni - sz[u];
    }
    cout << sz[v] << "\n";
    return sz[v];
}
#endif // cpismylifeOwO

int dis[MaxN];
priority_queue<pair<int, int>> group[5];

vector<int> createFunTour(int n, int Q)
{
    assert(Q >= 0);
    pair<int, int> cur = make_pair(n, 1);
    for (int x = 2; x <= n; x++)
    {
        int p = attractionsBehind(0, x - 1);
        if (p > n / 2)
        {
            cur = min(cur, make_pair(p, x));
        }
    }
    int r = cur.second;
    vector<int> af;
    for (int x = 1; x <= n; x++)
    {
        if (x != r)
        {
            dis[x] = hoursRequired(r - 1, x - 1);
        }
        if (dis[x] == 1)
        {
            af.push_back(x);
        }
    }
    for (int x = 1; x <= n; x++)
    {
        if (x != r)
        {
            bool done = false;
            for (int y = 0; y < (int)af.size() - 1; y++)
            {
                int v = af[y];
                if (hoursRequired(v - 1, x - 1) + 1 == dis[x])
                {
                    group[y].push(make_pair(dis[x], x));
                    //cout << x << " " << y << "\n";
                    done = true;
                }
            }
            if (!done)
            {
                group[(int)af.size() - 1].push(make_pair(dis[x], x));
                //cout << x << " " << (int)af.size() - 1 << "\n";
            }
        }
    }
    vector<int> res;
    int curm = -1;
    if ((int)af.size() == 3)
    {
        while (2 * max(group[0].size(), max(group[1].size(), group[2].size())) != group[0].size() + group[1].size() + group[2].size())
        {
            if (2 * max(group[0].size(), max(group[1].size(), group[2].size())) > group[0].size() + group[1].size() + group[2].size())
            {
                int p = 0;
                for (int x = 0; x < 3; x++)
                {
                    if (max(group[0].size(), max(group[1].size(), group[2].size())) == group[x].size())
                    {
                        p = x;
                        break;
                    }
                }
                curm = p;
                res.push_back(group[p].top().second - 1);
                group[p].pop();
                continue;
            }
            pair<pair<int, int>, int> now = make_pair(make_pair(0, 0), 0);
            for (int x = 0; x < 3; x++)
            {
                if (curm != x && !group[x].empty())
                {
                    now = max(now, make_pair(group[x].top(), x));
                }
            }
            curm = now.second;
            group[now.second].pop();
            res.push_back(now.first.second - 1);
        }
        if (group[1].size() > group[0].size())
        {
            swap(group[0], group[1]);
            if (curm == 0 || curm == 1)
            {
                curm ^= 1;
            }
        }
        if (group[2].size() > group[0].size())
        {
            swap(group[2], group[0]);
            if (curm == 0 || curm == 2)
            {
                curm ^= 2;
            }
        }
        while (!group[2].empty())
        {
            group[1].push(group[2].top());
            group[2].pop();
        }
        if (curm == 2)
        {
            curm = 1;
        }
    }
    if ((int)group[0].size() != (int)group[1].size())
    {
        if ((int)group[0].size() < (int)group[1].size())
        {
            swap(group[0], group[1]);
        }
        curm = 0;
        while ((int)group[0].size() != (int)group[1].size())
        {
            res.push_back(group[0].top().second - 1);
            group[0].pop();
        }
    }
    while (!group[0].empty() || !group[1].empty())
    {
        pair<pair<int, int>, int> now = make_pair(make_pair(0, 0), 0);
        for (int x = 0; x < 2; x++)
        {
            if (curm != x && !group[x].empty())
            {
                now = max(now, make_pair(group[x].top(), x));
            }
        }
        curm = now.second;
        group[now.second].pop();
        res.push_back(now.first.second - 1);
    }
    res.push_back(r - 1);
    return res;
}

#ifdef cpismylifeOwO
void Exc()
{
    PreDFS(1, -1);
    Build();
    vector<int> res = createFunTour(ni, 4e5);
    for (int x : res)
    {
        cout << x << " ";
    }
}

int main()
{
    freopen("FUN.INP", "r", stdin);
    //freopen("FUN.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}
#endif // cpismylifeOwO

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34