oj.uz

Submission #464119

# Submission time Handle Problem Language Result Execution time Memory
464119 2021-08-12T12:04:27 Z TeaTime Unique Cities (JOI19_ho_t5) C++17
0 / 100
 371 ms 47780 KB 
//#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, 0);
    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());

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

        cout << sv[i][0][0].first - sv[i][0][1].first << "\n";
    }

    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Incorrect 7 ms 10060 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 225 ms 36976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 371 ms 47780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Incorrect 7 ms 10060 KB Output isn't correct
3 Halted 0 ms 0 KB -