Submission #464125

#	Time	Username	Problem	Language	Result	Execution time	Memory
464125		TeaTime	Unique Cities (JOI19_ho_t5)	C++17	0 / 100	394 ms	43468 KiB

joi2019_ho_t5

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

const ll SZ = 2e5 + 100;
vector<vector<ll>> gr;
vector<ll> cols;
int dists[SZ];
ll n, m;

void dfs(int v, int par = -1) {
    for (auto to : gr[v]) {
        if (to != par) {
            dists[to] = dists[v] + 1;
            dfs(to, v);
        }
    }
}
pair<ll, ll> find_dim() {
    dists[0] = 0;
    dfs(0);
    pair<int, int> bst = { -1, -1 };
    for (int i = 0; i < n; i++) bst = max(bst, make_pair(dists[i], i));

    dists[bst.second] = 0;
    dfs(bst.second);

    pair<int, int> bst2 = { -1, -1 };
    for (int i = 0; i < n; i++) bst2 = max(bst2, make_pair(dists[i], i));

    return { bst.second, bst2.second };
}

vector<pair<ll, ll>> sv[SZ][2];
void dp(int v, int par, int ind) {
    pair<ll, ll> vrt = { 0, v };
    for (auto to : gr[v]) {
        if (to != par) {
            dp(to, v, ind);
            for (auto k : sv[to][ind]) sv[v][ind].push_back(make_pair(k.first + 1, k.second));
        }
    }

    sv[v][ind].push_back(vrt);
    sort(sv[v][ind].rbegin(), sv[v][ind].rend());

    while (sv[v][ind].size() > 2) sv[v][ind].pop_back();
}

signed main() {
    fastInp;

    cin >> n >> m;

    gr.resize(n);
    for (int i = 0; i < n - 1; i++) {
        ll u, v;
        cin >> u >> v;
        u--; v--;
        gr[u].push_back(v);
        gr[v].push_back(u);
    }

    cols.resize(n);
    for (auto& c : cols) cin >> c;

    pair<ll, ll> dim = find_dim();

    dp(dim.first, -1, 1);
    for (int i = 0; i < n; i++) {
        for (auto k : sv[i][1]) sv[i][0].push_back(k);

        sort(sv[i][0].rbegin(), sv[i][0].rend());
        sv[i][1].clear();
        auto it = unique(sv[i][0].begin(), sv[i][0].end());
        sv[i][0].erase(it, sv[i][0].end());

        while (sv[i][0].size() > 2) sv[i][0].pop_back();
    }
    dp(dim.second, -1, 1);
    for (int i = 0; i < n; i++) {
        for (auto k : sv[i][1]) sv[i][0].push_back(k);

        sort(sv[i][0].rbegin(), sv[i][0].rend());
        sv[i][1].clear();
        auto it = unique(sv[i][0].begin(), sv[i][0].end());
        sv[i][0].erase(it, sv[i][0].end());

        while (sv[i][0].size() > 2) sv[i][0].pop_back();
    }

    /*for (int i = 0; i < 30; i++) {
        ll v = rand() % n;
        dp(v, -1, 1);
        for (auto k : sv[i][1]) sv[i][0].push_back(k);

        sort(sv[i][0].rbegin(), sv[i][0].rend());

        while (sv[i][0].size() > 2) sv[i][0].pop_back();
    }*/
    for (int i = 0; i < n; i++) {
        cout << ((sv[i][0][0].first - sv[i][0][1].first) > 0) << "\n";
    }

    return 0;
}

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