oj.uz

Submission #494764

# Submission time Handle Problem Language Result Execution time Memory
494764 2021-12-16T07:01:49 Z dannyboy20031204 Balanced Tree (info1cup18_balancedtree) C++17
0 / 100
 4000 ms 33208 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair 
using namespace std;
void db() {cout << endl;}
template <typename T, typename ...U> void db(T a, U ...b) {
    //return;
    cout << a << ' ', db(b...);
}
#ifdef Cloud
#define file freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define file ios::sync_with_stdio(false); cin.tie(0)
#endif
const int N = 3001, inf = 1e9 + 1;
void solve(){
    int n;    
    cin >> n;
    vector<int> a(n);
    vector<int> g[n + 1];
    for (int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 0; i < n; i++) cin >> a[i];
    auto solve2 = [&](int _c, vector<int> c){
        queue<int> q;
        int dis[n + 1]{}, vis[n + 1]{}, mi[n + 1], par[n + 1]{};
        for (int &i : mi) i = inf;
        for (int i = 1; i <= n; i++) if (c[i - 1] == _c) {
            vis[i] = 1;
            par[i] = i;
            q.push(i);
        }
        while (!q.empty()){
            int u = q.front();
            q.pop();
            for (int i : g[u]){
                if (par[i] == par[u]) continue;
                if (vis[i]){
                    mi[par[u]] = min(mi[par[u]], dis[u] + dis[i] + 1);
                    mi[par[i]] = min(mi[par[i]], dis[u] + dis[i] + 1);
                }
                else{
                    dis[i] = dis[u] + 1;
                    vis[i] = 1;
                    par[i] = par[u];
                    q.push(i);
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) if (par[i] == i) ans = max(ans, mi[i]);
        return ans;
    };
    int ans = inf, tar = 0;
    for (int i = 0; i < (1 << n); i++){
        vector<int> b;
        for (int j = 0; j < n; j++) b.push_back(i >> j & 1);
        bool imp = 0;
        for (int i = 0; i < n; i++){
            if(a[i] != b[i] and a[i] != -1) imp = 1;
        }
        if (imp) continue;
        int tmp = max(solve2(0, b), solve2(1, b));
        if (tmp < ans){
            ans = tmp;
            tar = i;
        }
    }
    if (ans >= n) return void(cout << -1 << '\n');
    cout << ans << '\n';
    for (int i = 0; i < n; i++) cout << (tar >> i & 1) << ' ';
    cout << '\n';
}
signed main(){
    file;
    int t;
    cin >> t;
    while (t--)
        solve();
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1734 ms 340 KB Output is correct
2 Execution timed out 4056 ms 464 KB Time limit exceeded

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 964 KB Output isn't correct
2 Execution timed out 4045 ms 4540 KB Time limit exceeded
3 Execution timed out 4056 ms 1356 KB Time limit exceeded

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4059 ms 332 KB Time limit exceeded
2 Incorrect 39 ms 7620 KB Output isn't correct
3 Execution timed out 4049 ms 3232 KB Time limit exceeded

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 2444 KB Output isn't correct
2 Incorrect 151 ms 944 KB Output isn't correct
3 Execution timed out 4070 ms 492 KB Time limit exceeded
4 Execution timed out 4075 ms 588 KB Time limit exceeded
5 Execution timed out 4054 ms 716 KB Time limit exceeded
6 Incorrect 168 ms 1464 KB Output isn't correct
7 Incorrect 131 ms 844 KB Output isn't correct
8 Execution timed out 4066 ms 460 KB Time limit exceeded
9 Execution timed out 4051 ms 460 KB Time limit exceeded

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1734 ms 340 KB Output is correct
2 Execution timed out 4056 ms 464 KB Time limit exceeded
3 Incorrect 37 ms 964 KB Output isn't correct
4 Execution timed out 4045 ms 4540 KB Time limit exceeded
5 Execution timed out 4056 ms 1356 KB Time limit exceeded
6 Execution timed out 4059 ms 332 KB Time limit exceeded
7 Incorrect 39 ms 7620 KB Output isn't correct
8 Execution timed out 4049 ms 3232 KB Time limit exceeded
9 Incorrect 37 ms 2444 KB Output isn't correct
10 Incorrect 151 ms 944 KB Output isn't correct
11 Execution timed out 4070 ms 492 KB Time limit exceeded
12 Execution timed out 4075 ms 588 KB Time limit exceeded
13 Execution timed out 4054 ms 716 KB Time limit exceeded
14 Incorrect 168 ms 1464 KB Output isn't correct
15 Incorrect 131 ms 844 KB Output isn't correct
16 Execution timed out 4066 ms 460 KB Time limit exceeded
17 Execution timed out 4051 ms 460 KB Time limit exceeded
18 Execution timed out 4059 ms 1248 KB Time limit exceeded
19 Incorrect 169 ms 7940 KB Output isn't correct
20 Execution timed out 4030 ms 1240 KB Time limit exceeded
21 Incorrect 272 ms 33208 KB Output isn't correct
22 Execution timed out 4058 ms 23020 KB Time limit exceeded