oj.uz

Submission #286289

# Submission time Handle Problem Language Result Execution time Memory
286289 2020-08-30T09:18:08 Z gratus907 Village (BOI20_village) C++17
12 / 100
 6 ms 5352 KB 
#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 <vector<int>> D;
vector <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].back()], maxarr[D[i].back()]);
                D[cur].pop_back();
                D[i].pop_back();
            }
            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

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::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for (int i = 0; i<D.size(); i++)
      |                     ~^~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2688 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2688 KB Output is correct
17 Correct 2 ms 2688 KB Output is correct

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 5352 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2688 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2688 KB Output is correct
17 Correct 2 ms 2688 KB Output is correct
18 Runtime error 6 ms 5352 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -