Submission #762482

#	Time	Username	Problem	Language	Result	Execution time	Memory
762482		sysia	Unique Cities (JOI19_ho_t5)	C++17	0 / 100	652 ms	45396 KiB

joi2019_ho_t5

//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef pair<int, int> T;
const int oo = 1e9+7, oo2 = 1e9+7, K = 20;


vector<int>ord, dist, onpath;
void get_order(int L, int R, int n, vector<vector<int>>&g){
    vector<int>par(n+1);
    function<void(int, int)>dfs = [&](int v, int pa){
        par[v] = pa;
        for (auto x: g[v]){
            if (x == pa) continue;
            dfs(x, v);
        }
    };
    dfs(L, -1);
    vector<int>path;
    int now = R;
    while (now != -1){
        path.emplace_back(now);
        now = par[now];
    }
    reverse(path.begin(), path.end());
    dist.resize(n+1);
    function<void(int, int, int, int)>dfs2 = [&](int v, int p1, int p2, int d){
        ord.emplace_back(v);
        dist[v] = d;
        for (auto x: g[v]){
            if (x == p1 || x == p2) continue;
            dfs2(x, v, -1, d+1);
        }
    };
    onpath.assign(n+1, 0);
    for (int i = 0; i<(int)path.size(); i++){
        onpath[path[i]] = 1;
        dfs2(path[i], (i ? path[i-1] : -1), (i+1 < (int)path.size() ? path[i+1] : -1), 0);
    }
}

struct Tree{
    vector<int>tab, lazy;
    int size = 1, cnt = 0;

    Tree(int n){
        while (size < n) size*=2;
        tab.assign(2*size, 0);
        lazy.assign(2*size, -oo);
    }

    void push(int x){
        if (lazy[x] == -oo) return;
        for (auto k: {2*x, 2*x+1}){
            tab[k] = tab[x];
            lazy[k] = tab[x];
        }
        lazy[x] = -oo;
    }

    void print(int n){
        for (int i = 1; i<=n; i++){
            cerr << query(1, 0, size-1, i, i) << " ";
        }
        cerr << "\n";
    }

    void update(int x, int lx, int rx, int l, int r, int v){
        if (lx > r || rx < l) return;
        if (lx >= l && rx <= r){
            tab[x] = v;
            lazy[x] = v;
            return;
        }
        push(x);
        int m = (lx+rx)/2;
        update(2*x, lx, m, l, r, v);
        update(2*x+1, m+1, rx, l, r, v);
        tab[x] = max(tab[2*x], tab[2*x+1]);
    }
    
    int query(int x, int lx, int rx, int l, int r){
        if (lx > r || rx < l) return -oo;
        if (lx >= l && rx <= r) return tab[x];
        push(x);
        int m = (lx+rx)/2;
        return max(query(2*x, lx, m, l, r), query(2*x+1, m+1, rx, l, r));
    }
};

void solve(){
    int n, m; cin >> n >> m;
    vector<vector<int>>g(n+1);
    for (int i = 1; i<n; i++){
        int a, b; cin >> a >> b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    vector<int>c(n+1);
    for (int i = 1; i<=n; i++) cin >> c[i];
    int r = -1;
    for (int i = 1; i<=n; i++){
        if ((int)g[i].size() > 2){
            r = i;
            break;
        }
    }
    vector<int>where(n+1);
    if (r == -1){
        //sciezka
        for (int i = 1; i<=n; i++){
            if ((int)g[i].size() == 1){
                r = i;
                break;
            }
        }

        function<void(int, int)>dfessa = [&](int v, int pa){
            ord.emplace_back(v);
            for (auto x: g[v]){
                if (x == pa) continue;
                dfessa(x, v);
            }
        };
        dfessa(r, r);
        vector<int>ans(n+1);
        for (int i = 0; i<(int)ord.size(); i++){
            if ((n&1) && n/2 == i){
                ;
            } else {
                ans[ord[i]] = 1;
            }
        }
        for (int i = 1; i<=n; i++) cout << ans[i] << "\n";
        return;
    }
    debug(r);
    vector up(n+1, vector<int>(K));
    vector<int>depth(n+1);
    function<void(int, int, int)>dfs = [&](int v, int pa, int last){
        up[v][0] = pa;
        for (int i = 1; i<K; i++) up[v][i] = up[up[v][i-1]][i-1];
        if ((int)g[v].size() >= 3) last = v;
        if ((int)g[v].size() == 1) where[v] = last;
        for (auto x: g[v]){
            if (x == pa) continue;
            depth[x] = depth[v]+1;
            dfs(x, v, last);
        }
    };
    dfs(r, r, r);
    debug(where);
    T mx = {-oo, -oo};
    for (int i = 1; i<=n; i++) mx = max(mx, {depth[i], i});
    int L = mx.second;
    vector<int>D(n+1);
    function<void(int, int)>depthdfs = [&](int v, int pa){
        for (auto x: g[v]){
            if (x == pa) continue;
            D[x] = D[v]+1;
            depthdfs(x, v);
        }
    };
    depthdfs(L, L);
    mx = {-oo, -oo};
    for (int i = 1; i<=n; i++) mx = max(mx, {D[i], i});
    int R = mx.second;
    debug(L, R);
    auto lca = [&](int a, int b){
        if (depth[a] < depth[b]) swap(a, b);
        for (int i = K-1; i>=0; i--){
            if (depth[a] - (1<<i) >= depth[b]){
                a = up[a][i];
            }
        }
        if (a == b) return a;
        for (int i = K-1; i>=0; i--){
            if (up[a][i] != up[b][i]){
                a = up[a][i];
                b = up[b][i];
            }
        }
        return up[a][0];
    };
    auto dist2 = [&](int a, int b){
        return depth[a] + depth[b] - 2 * depth[lca(a, b)];
    };
    get_order(L, R, n, g);
    debug(ord);
    debug(dist);
    Tree left(n+2), right(n+2);
    for (int i = 1; i<=n; i++){
        if (i == R) continue;
        right.update(1, 0, right.size-1, i, i, dist2(L, i));
    }
    right.print(n);
    left.update(1, 0, left.size-1, 1, n, -oo);
    vector<T>ile(n+1);
    for (int k = 0; k < n; k++){
        int v = ord[k];
        int d1 = dist2(v, L);
        int d2 = dist2(v, R);
        debug(v, d1, d2);
        if (d1 == d2) continue;
        if (d1 > d2){
            //L ma dalej
            //szukamy drugiego najdluzszego dystansu
            d2 = max(d2, left.cnt+left.query(1, 0, left.size-1, 1, n));
        } else {
            d1 = max(d1, right.cnt+right.query(1, 0, right.size-1, 1, n));
        }
        debug(v, d1, d2);
        ile[v].first = abs(d1-d2);
        ile[v].second = (d1 > d2 ? L : R);
        if (k+1 < n && onpath[ord[k+1]]){
            right.cnt--;
            left.cnt++;
            if (v == L) continue;
            int now = -1;
            for (int ptr = k; ptr >= 0; ptr--){
                if (onpath[ord[ptr]]) {
                    now = ptr;
                    break;
                }
            }
            assert(now != -1);
            for (int ptr = k-1; ptr >= now; ptr--){
                left.update(1, 0, left.size-1, ord[ptr], ord[ptr], dist[ord[ptr]]);
            }
        }
    }
    debug(ile);
    for (int i = 1; i<=n; i++){
        if ((int)g[i].size() == 1 || ile[i].first >= 1){
            cout << "1\n";
        } else {
            cout << "0\n";
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32