oj.uz

Submission #400628

# Submission time Handle Problem Language Result Execution time Memory
400628 2021-05-08T12:30:25 Z dolphingarlic Balanced Tree (info1cup18_balancedtree) C++14
0 / 100
 502 ms 43548 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() - 1; ~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 = 1;

        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
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 2636 KB Output isn't correct
2 Incorrect 82 ms 2748 KB Output isn't correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 3664 KB Output isn't correct
2 Correct 89 ms 7108 KB Output is correct
3 Incorrect 74 ms 4672 KB Output isn't correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 4172 KB Output isn't correct
2 Incorrect 127 ms 43548 KB Output isn't correct
3 Incorrect 77 ms 20540 KB Output isn't correct

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 5368 KB Invalid color
2 Incorrect 69 ms 3940 KB Invalid color
3 Incorrect 69 ms 4080 KB Invalid color
4 Incorrect 63 ms 3608 KB Output isn't correct
5 Incorrect 57 ms 3780 KB Output isn't correct
6 Incorrect 71 ms 4412 KB Output isn't correct
7 Incorrect 73 ms 4168 KB Invalid color
8 Incorrect 63 ms 3656 KB Output isn't correct
9 Incorrect 71 ms 3760 KB Invalid color

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 2636 KB Output isn't correct
2 Incorrect 82 ms 2748 KB Output isn't correct
3 Incorrect 68 ms 3664 KB Output isn't correct
4 Correct 89 ms 7108 KB Output is correct
5 Incorrect 74 ms 4672 KB Output isn't correct
6 Incorrect 70 ms 4172 KB Output isn't correct
7 Incorrect 127 ms 43548 KB Output isn't correct
8 Incorrect 77 ms 20540 KB Output isn't correct
9 Incorrect 86 ms 5368 KB Invalid color
10 Incorrect 69 ms 3940 KB Invalid color
11 Incorrect 69 ms 4080 KB Invalid color
12 Incorrect 63 ms 3608 KB Output isn't correct
13 Incorrect 57 ms 3780 KB Output isn't correct
14 Incorrect 71 ms 4412 KB Output isn't correct
15 Incorrect 73 ms 4168 KB Invalid color
16 Incorrect 63 ms 3656 KB Output isn't correct
17 Incorrect 71 ms 3760 KB Invalid color
18 Incorrect 375 ms 10520 KB Output isn't correct
19 Incorrect 502 ms 16452 KB Output isn't correct
20 Incorrect 315 ms 7620 KB Output isn't correct
21 Runtime error 5 ms 5168 KB Execution killed with signal 11
22 Runtime error 129 ms 7932 KB Execution killed with signal 11