oj.uz

Submission #400647

# Submission time Handle Problem Language Result Execution time Memory
400647 2021-05-08T12:47:20 Z dolphingarlic Balanced Tree (info1cup18_balancedtree) C++14
23 / 100
 636 ms 42208 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int INF = 1e9;

vector<int> graph[100001];
int c[100001], black, white, opt[100001], dp[2][100001];
pair<int, int> dfs_res[100001];

pair<int, int> dfs1(int node = 1, int parent = 1) {
    pair<int, int> ans = {INF, INF};
    if (c[node]) {
        dp[0][node] = 0;
        dp[1][node] = INF;
        ans.second = 0;
    } else {
        dp[1][node] = 0;
        dp[0][node] = INF;
        ans.first = 0;
    }

    for (int i : graph[node])
        if (i != parent) {
            pair<int, int> ret = dfs1(i, node);
            ans.first = min(ans.first, ret.first + 1);
            ans.second = min(ans.second, ret.second + 1);
            dp[0][node] = min(dp[0][node], ret.first + 1);
            dp[1][node] = min(dp[1][node], ret.second + 1);
        }
    return dfs_res[node] = ans;
}

void dfs2(int node = 1, int parent = 0, int to_black = INF,
          int to_white = INF) {
    dp[0][node] = min(dp[0][node], to_black + 1);
    dp[1][node] = min(dp[1][node], to_white + 1);

    vector<int> to_black_pref = {INF}, to_black_suff = {INF}, to_white_pref = {INF}, to_white_suff = {INF};
    for (int i : graph[node]) if (i != parent) {
        to_black_pref.push_back(dfs_res[i].first);
        to_black_suff.push_back(dfs_res[i].first);
        to_white_pref.push_back(dfs_res[i].second);
        to_white_suff.push_back(dfs_res[i].second);
    }
    for (int i = 1; i < to_black_pref.size(); i++) {
        to_black_pref[i] = min(to_black_pref[i], to_black_pref[i - 1]);
        to_white_pref[i] = min(to_white_pref[i], to_white_pref[i - 1]);
    }
    for (int i = to_black_suff.size() - 2; ~i; i--) {
        to_black_suff[i] = min(to_black_suff[i], to_black_suff[i + 1]);
        to_white_suff[i] = min(to_white_suff[i], to_white_suff[i + 1]);
    }
    to_black_suff.push_back(INF);
    to_white_suff.push_back(INF);

    int idx = 1;
    for (int i : graph[node]) if (i != parent) {
        int new_to_black = min({to_black + 1, to_black_pref[idx - 1] + 1, to_black_suff[idx + 1] + 1});
        int new_to_white = min({to_white + 1, to_white_pref[idx - 1] + 1, to_white_suff[idx + 1] + 1});
        if (c[node] == 0) new_to_black = 0;
        if (c[node] == 1) new_to_white = 0;

        dfs2(i, node, new_to_black, new_to_white);
        idx++;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) graph[i].clear();
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        black = 0, white = 0;
        for (int i = 1; i <= n; i++) {
            cin >> c[i];
            if (n <= 17) {
                black <<= 1, white <<= 1;
                if (c[i] == 0) black++;
                if (c[i] == 1) white++;
            } else {
                opt[i] = c[i];
            }
        }

        if (n <= 17) {
            int ans = INF;
            for (int mask = 0; mask < (1 << n); mask++) {
                if ((black & ~mask) == black && (white & mask) == white) {
                    for (int i = 1; i <= n; i++)
                        c[n - i + 1] = (mask & (1 << i - 1)) >> (i - 1);
                    dfs1();
                    dfs2();
                    int pot = max(*max_element(dp[0] + 1, dp[0] + n + 1),
                                  *max_element(dp[1] + 1, dp[1] + n + 1));
                    if (pot < ans) {
                        ans = pot;
                        for (int i = 1; i <= n; i++) opt[i] = c[i];
                    }
                }
            }
            if (ans == INF) {
                cout << "-1\n";
            } else {
                cout << ans << '\n';
                for (int i = 1; i <= n; i++) cout << opt[i] << ' ';
                cout << '\n';
            }
        } else {
            dfs1();
            dfs2();
            int ans = max(*max_element(dp[0] + 1, dp[0] + n + 1),
                          *max_element(dp[1] + 1, dp[1] + n + 1));
            if (ans == INF) {
                cout << "-1\n";
            } else {
                cout << ans << '\n';
                for (int i = 1; i <= n; i++) cout << opt[i] << ' ';
                cout << '\n';
            }
        }
    }
    return 0;
}

Compilation message

balancedtree.cpp: In function 'void dfs2(int, int, int, int)':
balancedtree.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 1; i < to_black_pref.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~
balancedtree.cpp: In function 'int main()':
balancedtree.cpp:100:56: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  100 |                         c[n - i + 1] = (mask & (1 << i - 1)) >> (i - 1);
      |                                                      ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2700 KB Output is correct
2 Correct 88 ms 2696 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 2860 KB Output is correct
2 Correct 109 ms 5844 KB Output is correct
3 Correct 77 ms 3540 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 3064 KB Invalid color
2 Incorrect 138 ms 42208 KB Output isn't correct
3 Incorrect 81 ms 19436 KB Invalid color

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 4188 KB Invalid color
2 Incorrect 70 ms 2992 KB Invalid color
3 Incorrect 75 ms 3020 KB Invalid color
4 Incorrect 64 ms 2800 KB Invalid color
5 Incorrect 59 ms 2896 KB Output isn't correct
6 Incorrect 72 ms 3188 KB Output isn't correct
7 Incorrect 78 ms 3012 KB Invalid color
8 Incorrect 67 ms 2840 KB Output isn't correct
9 Incorrect 65 ms 2892 KB Invalid color

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2700 KB Output is correct
2 Correct 88 ms 2696 KB Output is correct
3 Correct 69 ms 2860 KB Output is correct
4 Correct 109 ms 5844 KB Output is correct
5 Correct 77 ms 3540 KB Output is correct
6 Incorrect 72 ms 3064 KB Invalid color
7 Incorrect 138 ms 42208 KB Output isn't correct
8 Incorrect 81 ms 19436 KB Invalid color
9 Incorrect 87 ms 4188 KB Invalid color
10 Incorrect 70 ms 2992 KB Invalid color
11 Incorrect 75 ms 3020 KB Invalid color
12 Incorrect 64 ms 2800 KB Invalid color
13 Incorrect 59 ms 2896 KB Output isn't correct
14 Incorrect 72 ms 3188 KB Output isn't correct
15 Incorrect 78 ms 3012 KB Invalid color
16 Incorrect 67 ms 2840 KB Output isn't correct
17 Incorrect 65 ms 2892 KB Invalid color
18 Incorrect 397 ms 4460 KB Output isn't correct
19 Incorrect 636 ms 9756 KB Output isn't correct
20 Incorrect 318 ms 3696 KB Output isn't correct
21 Runtime error 5 ms 5196 KB Execution killed with signal 11
22 Runtime error 128 ms 5912 KB Execution killed with signal 11