oj.uz

Submission #494763

# Submission time Handle Problem Language Result Execution time Memory
494763 2021-12-16T06:45:57 Z dannyboy20031204 Balanced Tree (info1cup18_balancedtree) C++17
13 / 100
 535 ms 40832 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;
    int c[n + 1];
    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 = 1; i <= n; i++) cin >> c[i];
    auto solve2 = [&](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] == _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 = max(solve2(0), solve2(1));
    if (ans >= n) return void(cout << -1 << '\n');
    cout << ans << '\n';
    for (int i = 1; i <= n; i++) cout << c[i] << ' ';
    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 Incorrect 4 ms 332 KB Invalid color
2 Incorrect 4 ms 332 KB Invalid color

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1212 KB Output is correct
2 Correct 53 ms 5300 KB Output is correct
3 Correct 45 ms 2328 KB Output is correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 1348 KB Output isn't correct
2 Incorrect 59 ms 9084 KB Output isn't correct
3 Incorrect 40 ms 4564 KB Invalid color

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 3020 KB Output isn't correct
2 Incorrect 45 ms 1476 KB Invalid color
3 Incorrect 41 ms 1600 KB Invalid color
4 Incorrect 33 ms 1220 KB Invalid color
5 Incorrect 32 ms 1352 KB Output isn't correct
6 Incorrect 41 ms 1868 KB Output isn't correct
7 Incorrect 52 ms 1556 KB Invalid color
8 Incorrect 34 ms 1256 KB Output isn't correct
9 Incorrect 34 ms 1316 KB Invalid color

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 332 KB Invalid color
2 Incorrect 4 ms 332 KB Invalid color
3 Correct 42 ms 1212 KB Output is correct
4 Correct 53 ms 5300 KB Output is correct
5 Correct 45 ms 2328 KB Output is correct
6 Incorrect 44 ms 1348 KB Output isn't correct
7 Incorrect 59 ms 9084 KB Output isn't correct
8 Incorrect 40 ms 4564 KB Invalid color
9 Incorrect 62 ms 3020 KB Output isn't correct
10 Incorrect 45 ms 1476 KB Invalid color
11 Incorrect 41 ms 1600 KB Invalid color
12 Incorrect 33 ms 1220 KB Invalid color
13 Incorrect 32 ms 1352 KB Output isn't correct
14 Incorrect 41 ms 1868 KB Output isn't correct
15 Incorrect 52 ms 1556 KB Invalid color
16 Incorrect 34 ms 1256 KB Output isn't correct
17 Incorrect 34 ms 1316 KB Invalid color
18 Incorrect 252 ms 2316 KB Output isn't correct
19 Incorrect 345 ms 9692 KB Output isn't correct
20 Incorrect 178 ms 1968 KB Output isn't correct
21 Incorrect 535 ms 40832 KB Output isn't correct
22 Incorrect 309 ms 25568 KB Output isn't correct