oj.uz

Submission #1094666

# Submission time Handle Problem Language Result Execution time Memory
1094666 2024-09-30T09:00:35 Z andrei_iorgulescu Village (BOI20_village) C++14
6 / 100
 4 ms 5224 KB 
#include <bits/stdc++.h>

using namespace std;

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 or it == 1)
        {
            //cout << it << endl;
            if (nrf[it] % 2 == 1)
            {
                vector<int> cn;
                for (auto itt : f[it])
                {
                    if (!scos[itt])
                        cn.push_back(itt), scos[itt] = true;
                }
                scos[it] = true;
                nrf[t[it]]--;
                ans_mic += 2;
                sol_mic[it] = cn[0];
                sol_mic[cn[0]] = it;
                for (int i = 1; i < cn.size(); i += 2)
                {
                    ans_mic += 4;
                    sol_mic[cn[i]] = cn[i + 1];
                    sol_mic[cn[i + 1]] = cn[i];
                }
            }
            else
            {
                vector<int> cn;
                for (auto itt : f[it])
                {
                    if (!scos[itt])
                        cn.push_back(itt), scos[itt] = true;
                }
                if (it != 1)
                {
                    for (int i = 0; i < cn.size(); i += 2)
                    {
                        ans_mic += 4;
                        sol_mic[cn[i]] = cn[i + 1];
                        sol_mic[cn[i + 1]] = cn[i];
                    }
                }
                else
                {
                    if (cn.size() == 0)
                    {
                        int x = f[1][0];
                        int y = sol_mic[x];
                        ans_mic += 2;
                        sol_mic[1] = x;
                        sol_mic[y] = 1;
                    }
                    else
                    {
                        int x = cn[0], y = cn[1];
                        ans_mic += 4;
                        sol_mic[x] = 1;
                        sol_mic[1] = y;
                        sol_mic[y] = x;
                        for (int i = 2; i < cn.size(); i += 2)
                        {
                            ans_mic += 4;
                            sol_mic[cn[i]] = cn[i + 1];
                            sol_mic[cn[i + 1]] = cn[i];
                        }
                    }
                }
            }
        }
    }
}

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 / 2 + 1;
    for (int i = 0; i < noduri.size(); i++)
    {
        int x = (i + ofs) % n;
        sol_mare[noduri[i]] = noduri[x];
    }
}

int 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

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

Subtask #1
6.0 / 12.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 4952 KB Partially correct
2 Correct 2 ms 4956 KB Output is correct
3 Partially correct 2 ms 4956 KB Partially correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 5180 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Partially correct 2 ms 4956 KB Partially correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 3 ms 4960 KB Output is correct
11 Partially correct 3 ms 5164 KB Partially correct
12 Partially correct 2 ms 4960 KB Partially correct
13 Partially correct 3 ms 5168 KB Partially correct
14 Correct 3 ms 4964 KB Output is correct
15 Partially correct 2 ms 4964 KB Partially correct
16 Partially correct 2 ms 4964 KB Partially correct
17 Partially correct 2 ms 4964 KB Partially correct

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 4964 KB Partially correct
2 Partially correct 2 ms 5220 KB Partially correct
3 Partially correct 3 ms 5220 KB Partially correct
4 Partially correct 3 ms 5216 KB Partially correct
5 Partially correct 4 ms 5220 KB Partially correct
6 Partially correct 3 ms 5212 KB Partially correct
7 Partially correct 2 ms 5168 KB Partially correct
8 Partially correct 3 ms 5216 KB Partially correct
9 Partially correct 3 ms 5208 KB Partially correct
10 Partially correct 3 ms 5220 KB Partially correct
11 Partially correct 3 ms 5220 KB Partially correct
12 Correct 4 ms 5224 KB Output is correct
13 Correct 2 ms 5224 KB Output is correct
14 Partially correct 3 ms 5224 KB Partially correct
15 Partially correct 2 ms 5224 KB Partially correct
16 Partially correct 3 ms 5224 KB Partially correct
17 Partially correct 2 ms 5224 KB Partially correct
18 Partially correct 4 ms 5224 KB Partially correct
19 Partially correct 3 ms 5224 KB Partially correct
20 Partially correct 4 ms 5224 KB Partially correct
21 Partially correct 2 ms 5224 KB Partially correct
22 Partially correct 2 ms 5224 KB Partially correct
23 Partially correct 2 ms 5212 KB Partially correct
24 Partially correct 2 ms 5212 KB Partially correct
25 Incorrect 2 ms 5212 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 4952 KB Partially correct
2 Correct 2 ms 4956 KB Output is correct
3 Partially correct 2 ms 4956 KB Partially correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 5180 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Partially correct 2 ms 4956 KB Partially correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 3 ms 4960 KB Output is correct
11 Partially correct 3 ms 5164 KB Partially correct
12 Partially correct 2 ms 4960 KB Partially correct
13 Partially correct 3 ms 5168 KB Partially correct
14 Correct 3 ms 4964 KB Output is correct
15 Partially correct 2 ms 4964 KB Partially correct
16 Partially correct 2 ms 4964 KB Partially correct
17 Partially correct 2 ms 4964 KB Partially correct
18 Partially correct 3 ms 4964 KB Partially correct
19 Partially correct 2 ms 5220 KB Partially correct
20 Partially correct 3 ms 5220 KB Partially correct
21 Partially correct 3 ms 5216 KB Partially correct
22 Partially correct 4 ms 5220 KB Partially correct
23 Partially correct 3 ms 5212 KB Partially correct
24 Partially correct 2 ms 5168 KB Partially correct
25 Partially correct 3 ms 5216 KB Partially correct
26 Partially correct 3 ms 5208 KB Partially correct
27 Partially correct 3 ms 5220 KB Partially correct
28 Partially correct 3 ms 5220 KB Partially correct
29 Correct 4 ms 5224 KB Output is correct
30 Correct 2 ms 5224 KB Output is correct
31 Partially correct 3 ms 5224 KB Partially correct
32 Partially correct 2 ms 5224 KB Partially correct
33 Partially correct 3 ms 5224 KB Partially correct
34 Partially correct 2 ms 5224 KB Partially correct
35 Partially correct 4 ms 5224 KB Partially correct
36 Partially correct 3 ms 5224 KB Partially correct
37 Partially correct 4 ms 5224 KB Partially correct
38 Partially correct 2 ms 5224 KB Partially correct
39 Partially correct 2 ms 5224 KB Partially correct
40 Partially correct 2 ms 5212 KB Partially correct
41 Partially correct 2 ms 5212 KB Partially correct
42 Incorrect 2 ms 5212 KB Output isn't correct
43 Halted 0 ms 0 KB -