Submission #286283

#	Time	Username	Problem	Language	Result	Execution time	Memory
286283		gratus907	Village (BOI20_village)	C++17	50 / 100	102 ms	21480 KiB

Village

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll long long
#define int ll
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;
int n;
vector<vector<int>> G;
vector<pii> edges;
int minval, maxval;
int minarr[101010], maxarr[101010];
vector <int> tp;
int par[101010];
int sub[101010];
int level[101010];
void aux(int rt, int p)
{
    level[rt] = level[p]+1;
    sub[rt]++;
    par[rt] = p;
    tp.push_back(rt);
    for (int nxt : G[rt])
    {
        if (nxt != p)
        {
            aux(nxt, rt);
            sub[rt] += sub[nxt];
        }
    }
}
void solve_min()
{
    int cnt = 0;
    aux(1, 0);
    par[1] = G[1].front();
    while(!tp.empty())
    {
        int cur = tp.back();
        if (minarr[cur] == cur)
        {
            swap(minarr[cur], minarr[par[cur]]);
            cnt += 2;
        }
        tp.pop_back();
    }
    minval = cnt;
    par[1] = 0;
    return;
}
pair<bool, int> is_center(int rt, int p)
{
    int max_sub = 0, sum_sub = 0, index = rt;
    for (int nxt : G[rt])
    {
        if (nxt != p)
        {
            if (max_sub <= sub[nxt])
            {
                max_sub = sub[nxt];
                index = nxt;
            }
            sum_sub += sub[nxt];
        }
    }
    if (n-1-sum_sub >= max_sub)
    {
        max_sub = n-1-sum_sub;
        index = par[rt];
    }
    return {max_sub <= n/2, index};
}
int center(int rt, int p)
{
    auto u = is_center(rt, p);
    if (u.first) return rt;
    else
    {
        return center(u.second, rt);
    }
}
vector <deque<int>> D;
deque <int> seats;
void alloc_seat(int rt, int p)
{
    seats.push_back(rt);
    for (int nxt : G[rt])
        if (nxt != p)
            alloc_seat(nxt, rt);
}
void solve_max()
{
    int cent = center(1, 0);
    for (pii e : edges)
    {
        int a = e.first, b = e.second;
        if (level[a] > level[b]) swap(a, b);
        int passes = 2*min(sub[b], n-sub[b]);
        maxval += passes;
    }
    memset(sub, 0, sizeof(sub));
    memset(par, 0, sizeof(par));
    memset(level, 0, sizeof(level));
    aux(cent, 0);
    sort(all(G[cent]), [](int a, int b)->bool{return sub[a] > sub[b];});
    for (int head : G[cent])
    {
        alloc_seat(head, cent);
        D.push_back(seats);
        seats.clear();
    }
    if (n%2 == 0)
        D.push_back({cent});
    /*for (int i = 0; i<D.size(); i++)
    {
        printf("D[%lld] : ",i);
        for (auto it:D[i])
            printf("%lld ",it);
        printf("\n");
    }*/
    for (int i = 0; i<D.size(); i++)
    {
        if (D[i].empty()) continue;
        int cur = i+1;
        while (!D[i].empty())
        {
            while ((D[cur].size() > 0) && (D[i].size() > 0))
            {
                if (D[cur].empty())
                    break;
                swap(maxarr[D[cur].front()], maxarr[D[i].front()]);
                D[cur].pop_front();
                D[i].pop_front();
            }
            cur++;
        }
    }
    if (n%2 != 0)
        swap(maxarr[cent], maxarr[G[cent].front()]);
}
int32_t main()
{
    usecppio
    cin >> n;
    G.resize(n+5);
    for (int i = 1; i<n; i++)
    {
        int u, v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
        edges.push_back({u, v});
    }
    for (int i = 1; i<=n; i++)
        minarr[i] = maxarr[i] = i;
    solve_min();
    //solve_max();
    cout << minval << ' ' << maxval << '\n';
    for (int i = 1; i<=n; i++)
        cout << minarr[i] << ' ';
    cout << '\n';
    for (int i = 1; i<=n; i++)
        cout << maxarr[i] << ' ';
    cout << '\n';
}

Compilation message (stderr)

Village.cpp: In function 'void solve_max()':
Village.cpp:123:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::deque<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for (int i = 0; i<D.size(); i++)
      |                     ~^~~~~~~~~

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50