oj.uz

Submission #494762

# Submission time Handle Problem Language Result Execution time Memory
494762 2021-12-16T06:33:11 Z dannyboy20031204 Balanced Tree (info1cup18_balancedtree) C++17
0 / 100
 537 ms 47340 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] = 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 3 ms 468 KB Invalid color
2 Incorrect 4 ms 328 KB Invalid color

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 1156 KB Output isn't correct
2 Incorrect 66 ms 5560 KB Output isn't correct
3 Incorrect 50 ms 2412 KB Output isn't correct

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 1392 KB Output isn't correct
2 Incorrect 84 ms 9460 KB Output isn't correct
3 Incorrect 55 ms 4576 KB Output isn't correct

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 3272 KB Output isn't correct
2 Incorrect 50 ms 1520 KB Invalid color
3 Incorrect 49 ms 1660 KB Invalid color
4 Incorrect 39 ms 1252 KB Output isn't correct
5 Incorrect 40 ms 1404 KB Output isn't correct
6 Incorrect 45 ms 2004 KB Invalid color
7 Incorrect 57 ms 1480 KB Output isn't correct
8 Incorrect 43 ms 1240 KB Output isn't correct
9 Incorrect 33 ms 1380 KB Output isn't correct

Subtask #5
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 468 KB Invalid color
2 Incorrect 4 ms 328 KB Invalid color
3 Incorrect 39 ms 1156 KB Output isn't correct
4 Incorrect 66 ms 5560 KB Output isn't correct
5 Incorrect 50 ms 2412 KB Output isn't correct
6 Incorrect 40 ms 1392 KB Output isn't correct
7 Incorrect 84 ms 9460 KB Output isn't correct
8 Incorrect 55 ms 4576 KB Output isn't correct
9 Incorrect 55 ms 3272 KB Output isn't correct
10 Incorrect 50 ms 1520 KB Invalid color
11 Incorrect 49 ms 1660 KB Invalid color
12 Incorrect 39 ms 1252 KB Output isn't correct
13 Incorrect 40 ms 1404 KB Output isn't correct
14 Incorrect 45 ms 2004 KB Invalid color
15 Incorrect 57 ms 1480 KB Output isn't correct
16 Incorrect 43 ms 1240 KB Output isn't correct
17 Incorrect 33 ms 1380 KB Output isn't correct
18 Incorrect 245 ms 8224 KB Output isn't correct
19 Incorrect 383 ms 15936 KB Output isn't correct
20 Incorrect 194 ms 5160 KB Output isn't correct
21 Incorrect 537 ms 47340 KB Output isn't correct
22 Incorrect 312 ms 31736 KB Output isn't correct