Submission #1174567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174567		Pacybwoah	Balanced Tree (info1cup18_balancedtree)	C++20	0 / 100	4097 ms	2000 KiB

balancedtree

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>
#include<cmath>
using namespace std;
typedef long long ll;
const int inf = 1e9;
vector<vector<int>> graph;
struct reroot{
    vector<int> vec, dp1, dp2;
    int n;
    reroot(int _n){
        n = _n;
        graph.resize(n + 1);
        vec.resize(n + 1);
        dp1.resize(n + 1);
        dp2.resize(n + 1);
    }
    void set_1(int x){
        vec[x] = 1;
    }
    void dfs1(int node, int parent){
        if(vec[node]) dp1[node] = 0;
        else dp1[node] = inf;
        for(auto &x: graph[node]){
            if(x == parent) continue;
            dfs1(x, node);
            dp1[node] = min(dp1[node], dp1[x] + 1);
        }
    }
    void dfs2(int node, int parent, int up){
        multiset<int> s;
        s.insert(up + 1);
        for(auto &x: graph[node]){
            if(x == parent) continue;
            s.insert(dp1[x] + 1);
        }
        dp2[node] = (*s.begin());
        if(vec[node]) s.insert(0);
        for(auto &x: graph[node]){
            if(x == parent) continue;
            s.erase(s.find(dp1[x] + 1));
            dfs2(x, node, (*s.begin()));
            s.insert(dp1[x] + 1);
        }
    }
    void do_dp(){
        dfs1(1, 1);
        dfs2(1, 1, inf);
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<vector<int>>().swap(graph);
        graph.resize(n + 1);
        for(int i = 1; i < n; i++){
            int a, b;
            cin >> a >> b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        vector<int> vec(n + 1);
        for(int i = 1; i <= n; i++) cin >> vec[i];
        int mini = inf, best = -1;
        for(int i = 0; i < (1 << n); i++){
            reroot zer(n), one(n);
            bool flag = 1;
            for(int j = 0; j < n; j++){
                if(i & (1 << j)){
                    if(vec[j + 1] == 0) flag = 0;
                    one.set_1(j + 1);
                }
                else{
                    if(vec[j + 1] == 1) flag = 0;
                    zer.set_1(j + 1);
                }
            }
            if(!flag) continue;
            int res = 0;
            zer.do_dp();
            one.do_dp();
            for(int j = 0; j < n; j++){
                if(i & (1 << j)){
                    res = max(res, one.dp2[j + 1]);
                }
                else{
                    res = max(res, zer.dp2[j + 1]);
                }
            }
            if(res < mini){
                mini = res;
                best = i;
            }
        }
        if(mini >= inf) cout << "-1\n";
        else{
            cout << mini << "\n";
            for(int j = 0; j < n; j++){
                if(best & (1 << j)) cout << "1 ";
                else cout << "0 ";
            }
            cout << "\n";
        }
    }
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run pD.cpp -g

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 26
• Subtask 4: 0 / 45
• Subtask 5: 0 / 6