oj.uz

Submission #447883

# Submission time Handle Problem Language Result Execution time Memory
447883 2021-07-28T00:25:31 Z Ozy Village (BOI20_village) C++17
50 / 100
 104 ms 23884 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define INF 1000000000000
#define MAX 100000

lli n,a,b,M,cent;
lli nh[MAX+2],des[MAX+2],dir[MAX+2],desmin[MAX+2];
vector<lli> hijos[MAX+2],orden,nuevo,grande;
lli dp[2][MAX+2];

lli Find(lli pos, lli padre,lli mitad) {

    lli grande = -1;
    for(auto h : hijos[pos]) {
        if (padre == h) continue;
        if (nh[h] > mitad) grande = h;
    }

    if (grande == -1) return pos;
    else return Find(grande,pos,mitad);

}

void DFS(lli pos, lli padre) {

    nh[pos] = 1;
    vector<lli> unos;
    lli MIN = INF;
    lli nodo;
    lli sum = 0;

    for (auto h : hijos[pos]) {
        if (h == padre) continue;

        DFS(h,pos);
        nh[pos] += nh[h];

        sum += min(dp[0][h], dp[1][h]);
        if (dp[0][h] == INF) swap(desmin[h], desmin[pos]);
        nodo = h;

    }

    if (nh[pos] == 1) {dp[1][pos]=2;dp[0][pos]=INF;}
    else {
        dp[0][pos] = sum;
        dp[1][pos] = sum+2;
        if (desmin[pos] == pos && pos == 1){
            swap(desmin[nodo], desmin[pos]);
            dp[0][pos] += 2;
        }
    }

    lli x = min(nh[pos],n-nh[pos]);
    M += x*2;
}

void agrega(lli pos, lli padre) {
    nuevo.push_back(pos);
    for (auto h : hijos[pos]) if (h != padre) agrega(h,pos);
}

void solve() {

    lli menor,mayor;
    menor = mayor = -1;
    orden.push_back(cent);

    for (auto h : hijos[cent]) {
        nuevo.clear();
        agrega(h,cent);

        if (menor == -1 || nuevo.size() < menor) menor = nuevo.size();
        if (mayor == -1 || nuevo.size() > mayor) {
            swap(nuevo,grande);
            mayor = grande.size();
        }

        if (nuevo.empty()) continue;
        for (auto act : nuevo) orden.push_back(act);
    }

    for (auto act : grande) orden.push_back(act);
    lli cont = 0;

    rep(i,orden.size()-mayor,orden.size()-1) des[orden[i]] = orden[cont++];
    rep(i,0,orden.size()-mayor-1) des[orden[i]] = orden[cont++];
}

void swapea(lli pos, lli padre, lli actual) {

    lli nodo,MIN = INF;
    vector<lli> unos;

    if (pos != 1 && hijos[pos].size() == 1) return;

    for (auto h : hijos[pos]) {
        if (h == padre) continue;

        if (dp[1][h] <= dp[0][h]) {unos.push_back(h); swapea(h,pos,1);}
        else if (dp[1][h]-dp[0][h] < MIN) {MIN = dp[1][h]-dp[0][h]; nodo = h; swapea(h,pos,0);}
    }

    if (actual == 0 && unos.empty()) {unos.push_back(nodo);}
    unos.push_back(pos);
    if (unos.size() == 1) return;

    rep(i,0,unos.size()-2) swap(dir[unos[i]],dir[unos[i+1]]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    rep(i,1,n-1) {
        cin >> a >> b;
        hijos[a].push_back(b);
        hijos[b].push_back(a);
        dir[i] = i;
    }
    dir[n] = n;
    rep(i, 1, n) desmin[i] = i;
    rep(i, 1, n) dp[0][i] = INF;

    DFS(1,0);
    cent = Find(1,0,n/2);

    solve();
    ///swapea(1,0,0);

    cout << dp[0][1] << ' '<< M <<endl;
    rep(i,1,n) cout << desmin[i] << ' ';
    cout << "\n";
    rep(i,1,n) cout << des[i] << ' ';

}

Compilation message

Village.cpp: In function 'void DFS(long long int, long long int)':
Village.cpp:35:9: warning: unused variable 'MIN' [-Wunused-variable]
   35 |     lli MIN = INF;
      |         ^~~
Village.cpp: In function 'void solve()':
Village.cpp:80:41: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   80 |         if (menor == -1 || nuevo.size() < menor) menor = nuevo.size();
      |                            ~~~~~~~~~~~~~^~~~~~~
Village.cpp:81:41: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   81 |         if (mayor == -1 || nuevo.size() > mayor) {
      |                            ~~~~~~~~~~~~~^~~~~~~
Village.cpp:4:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for (int i = (a); i <= (b); i++)
      |                                        ^
Village.cpp:93:5: note: in expansion of macro 'rep'
   93 |     rep(i,orden.size()-mayor,orden.size()-1) des[orden[i]] = orden[cont++];
      |     ^~~
Village.cpp:4:40: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
    4 | #define rep(i,a,b) for (int i = (a); i <= (b); i++)
      |                                        ^
Village.cpp:94:5: note: in expansion of macro 'rep'
   94 |     rep(i,0,orden.size()-mayor-1) des[orden[i]] = orden[cont++];
      |     ^~~
Village.cpp: In function 'void swapea(long long int, long long int, long long int)':
Village.cpp:4:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for (int i = (a); i <= (b); i++)
      |                                        ^
Village.cpp:115:5: note: in expansion of macro 'rep'
  115 |     rep(i,0,unos.size()-2) swap(dir[unos[i]],dir[unos[i+1]]);
      |     ^~~

Subtask #1
6.0 / 12.0

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

Subtask #2
19.0 / 38.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 2636 KB Partially correct
2 Partially correct 2 ms 2636 KB Partially correct
3 Partially correct 2 ms 2636 KB Partially correct
4 Partially correct 2 ms 2764 KB Partially correct
5 Partially correct 2 ms 2764 KB Partially correct
6 Partially correct 2 ms 2764 KB Partially correct
7 Partially correct 2 ms 2764 KB Partially correct
8 Partially correct 2 ms 2764 KB Partially correct
9 Partially correct 2 ms 2764 KB Partially correct
10 Correct 2 ms 2764 KB Output is correct
11 Partially correct 2 ms 2764 KB Partially correct
12 Correct 2 ms 2764 KB Output is correct
13 Correct 2 ms 2764 KB Output is correct
14 Correct 2 ms 2764 KB Output is correct
15 Correct 2 ms 2764 KB Output is correct
16 Partially correct 2 ms 2764 KB Partially correct
17 Correct 2 ms 2764 KB Output is correct
18 Correct 2 ms 2764 KB Output is correct
19 Correct 2 ms 2764 KB Output is correct
20 Correct 2 ms 2764 KB Output is correct
21 Correct 2 ms 2764 KB Output is correct
22 Correct 2 ms 2764 KB Output is correct
23 Partially correct 2 ms 2764 KB Partially correct
24 Partially correct 2 ms 2764 KB Partially correct
25 Partially correct 2 ms 2636 KB Partially correct
26 Partially correct 2 ms 2764 KB Partially correct
27 Partially correct 2 ms 2764 KB Partially correct
28 Partially correct 3 ms 2764 KB Partially correct
29 Partially correct 2 ms 2764 KB Partially correct
30 Correct 2 ms 2764 KB Output is correct

Subtask #3
25.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Partially correct 2 ms 2636 KB Partially correct
5 Partially correct 2 ms 2576 KB Partially correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Partially correct 2 ms 2636 KB Partially correct
12 Partially correct 2 ms 2636 KB Partially correct
13 Correct 2 ms 2636 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2636 KB Output is correct
16 Correct 2 ms 2636 KB Output is correct
17 Partially correct 2 ms 2636 KB Partially correct
18 Partially correct 2 ms 2636 KB Partially correct
19 Partially correct 2 ms 2636 KB Partially correct
20 Partially correct 2 ms 2636 KB Partially correct
21 Partially correct 2 ms 2764 KB Partially correct
22 Partially correct 2 ms 2764 KB Partially correct
23 Partially correct 2 ms 2764 KB Partially correct
24 Partially correct 2 ms 2764 KB Partially correct
25 Partially correct 2 ms 2764 KB Partially correct
26 Partially correct 2 ms 2764 KB Partially correct
27 Correct 2 ms 2764 KB Output is correct
28 Partially correct 2 ms 2764 KB Partially correct
29 Correct 2 ms 2764 KB Output is correct
30 Correct 2 ms 2764 KB Output is correct
31 Correct 2 ms 2764 KB Output is correct
32 Correct 2 ms 2764 KB Output is correct
33 Partially correct 2 ms 2764 KB Partially correct
34 Correct 2 ms 2764 KB Output is correct
35 Correct 2 ms 2764 KB Output is correct
36 Correct 2 ms 2764 KB Output is correct
37 Correct 2 ms 2764 KB Output is correct
38 Correct 2 ms 2764 KB Output is correct
39 Correct 2 ms 2764 KB Output is correct
40 Partially correct 2 ms 2764 KB Partially correct
41 Partially correct 2 ms 2764 KB Partially correct
42 Partially correct 2 ms 2636 KB Partially correct
43 Partially correct 2 ms 2764 KB Partially correct
44 Partially correct 2 ms 2764 KB Partially correct
45 Partially correct 3 ms 2764 KB Partially correct
46 Partially correct 2 ms 2764 KB Partially correct
47 Correct 2 ms 2764 KB Output is correct
48 Partially correct 80 ms 12852 KB Partially correct
49 Partially correct 104 ms 13500 KB Partially correct
50 Partially correct 78 ms 13732 KB Partially correct
51 Partially correct 57 ms 11272 KB Partially correct
52 Partially correct 97 ms 13516 KB Partially correct
53 Partially correct 67 ms 12544 KB Partially correct
54 Partially correct 40 ms 12988 KB Partially correct
55 Partially correct 102 ms 23884 KB Partially correct
56 Partially correct 91 ms 18876 KB Partially correct
57 Partially correct 91 ms 17116 KB Partially correct
58 Partially correct 85 ms 15664 KB Partially correct
59 Partially correct 82 ms 14140 KB Partially correct
60 Correct 62 ms 13256 KB Output is correct
61 Correct 63 ms 13596 KB Output is correct
62 Correct 70 ms 14308 KB Output is correct
63 Correct 66 ms 13396 KB Output is correct
64 Partially correct 72 ms 13760 KB Partially correct
65 Correct 70 ms 14196 KB Output is correct
66 Correct 64 ms 13308 KB Output is correct
67 Correct 50 ms 11004 KB Output is correct
68 Correct 59 ms 12284 KB Output is correct
69 Correct 71 ms 14788 KB Output is correct
70 Correct 66 ms 13212 KB Output is correct
71 Correct 46 ms 10708 KB Output is correct
72 Correct 52 ms 11736 KB Output is correct
73 Correct 78 ms 14544 KB Output is correct
74 Correct 65 ms 13220 KB Output is correct
75 Partially correct 80 ms 14216 KB Partially correct
76 Partially correct 76 ms 13992 KB Partially correct
77 Partially correct 76 ms 13748 KB Partially correct
78 Partially correct 46 ms 10140 KB Partially correct
79 Partially correct 57 ms 11276 KB Partially correct
80 Partially correct 88 ms 14120 KB Partially correct
81 Partially correct 78 ms 13724 KB Partially correct
82 Partially correct 71 ms 13504 KB Partially correct