oj.uz

Submission #546703

# Submission time Handle Problem Language Result Execution time Memory
546703 2022-04-08T08:32:58 Z Monarchuwu Unique Cities (JOI19_ho_t5) C++17
100 / 100
 411 ms 49176 KB 
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
#define ff first
#define ss second

const int N = 2e5 + 8;
int n, m;
vector<int> g[N];
int color[N];

int dp[N], dep[N], ptr;
void dfs_len(int u, int p = 0) {
    dp[u] = dep[u] = dep[p] + 1;
    if (dep[ptr] < dep[u]) ptr = u;

    for (int v : g[u]) if (v != p) {
        dfs_len(v, u);
        dp[u] = max(dp[u], dp[v]);
    }
}

int cnt[N], cnt_unique, ans[N];
vector<int> A;
void add(int x) {
    if (++cnt[color[x]] == 1) ++cnt_unique;
    A.push_back(x);
}
void del() {
    int x = A.back(); A.pop_back();
    if (--cnt[color[x]] == 0) --cnt_unique;
}
void dfs(int u, int p = 0) {
    if (p) add(p);
    vector<pii> vec;
    for (int v : g[u]) if (v != p) vec.emplace_back(dp[v], v);
    sort(vec.begin(), vec.end(), greater<pii>());

    int mx1 = vec.size() > 0 ? vec[0].ff : 0;
    int mx2 = vec.size() > 1 ? vec[1].ff : 0;
    for (pii v : vec) {
        int mx = mx1 + mx2 - max(v.ff, mx2);
        while (!A.empty() && mx - dep[u] >= dep[u] - dep[A.back()]) del();
        dfs(v.ss, u);
    }

    while (!A.empty() && dp[u] - dep[u] >= dep[u] - dep[A.back()]) del();
    ans[u] = max(ans[u], cnt_unique);
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) cin >> color[i];

    dfs_len(ptr = 1);
    for (int k = 0, i; k < 2; ++k) {
        dfs_len(i = ptr);
        dfs(i);
    }
    for (int i = 1; i <= n; ++i) cout << ans[i] << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5172 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5300 KB Output is correct
5 Correct 6 ms 5076 KB Output is correct
6 Correct 6 ms 5460 KB Output is correct
7 Correct 4 ms 5204 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 4 ms 5168 KB Output is correct
11 Correct 4 ms 5096 KB Output is correct
12 Correct 4 ms 5204 KB Output is correct
13 Correct 4 ms 5428 KB Output is correct
14 Correct 4 ms 5168 KB Output is correct
15 Correct 4 ms 5168 KB Output is correct
16 Correct 4 ms 5204 KB Output is correct
17 Correct 4 ms 5300 KB Output is correct
18 Correct 4 ms 5204 KB Output is correct
19 Correct 5 ms 5076 KB Output is correct
20 Correct 5 ms 5460 KB Output is correct
21 Correct 5 ms 5236 KB Output is correct
22 Correct 5 ms 5180 KB Output is correct
23 Correct 5 ms 5224 KB Output is correct
24 Correct 4 ms 5204 KB Output is correct
25 Correct 4 ms 5096 KB Output is correct
26 Correct 4 ms 5108 KB Output is correct
27 Correct 4 ms 5296 KB Output is correct
28 Correct 4 ms 5332 KB Output is correct
29 Correct 4 ms 5204 KB Output is correct
30 Correct 4 ms 5120 KB Output is correct
31 Correct 4 ms 5296 KB Output is correct
32 Correct 5 ms 5232 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 10776 KB Output is correct
2 Correct 188 ms 28872 KB Output is correct
3 Correct 23 ms 8780 KB Output is correct
4 Correct 317 ms 17856 KB Output is correct
5 Correct 393 ms 46680 KB Output is correct
6 Correct 392 ms 32008 KB Output is correct
7 Correct 289 ms 18220 KB Output is correct
8 Correct 361 ms 20752 KB Output is correct
9 Correct 280 ms 19956 KB Output is correct
10 Correct 289 ms 19824 KB Output is correct
11 Correct 210 ms 21656 KB Output is correct
12 Correct 334 ms 35692 KB Output is correct
13 Correct 349 ms 32336 KB Output is correct
14 Correct 295 ms 31360 KB Output is correct
15 Correct 179 ms 21740 KB Output is correct
16 Correct 371 ms 37844 KB Output is correct
17 Correct 294 ms 32688 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 13524 KB Output is correct
2 Correct 341 ms 47168 KB Output is correct
3 Correct 32 ms 9484 KB Output is correct
4 Correct 320 ms 19520 KB Output is correct
5 Correct 401 ms 49176 KB Output is correct
6 Correct 347 ms 33924 KB Output is correct
7 Correct 327 ms 19652 KB Output is correct
8 Correct 319 ms 25584 KB Output is correct
9 Correct 364 ms 23640 KB Output is correct
10 Correct 312 ms 21868 KB Output is correct
11 Correct 319 ms 21232 KB Output is correct
12 Correct 366 ms 43208 KB Output is correct
13 Correct 386 ms 32392 KB Output is correct
14 Correct 362 ms 32736 KB Output is correct
15 Correct 208 ms 22680 KB Output is correct
16 Correct 286 ms 40188 KB Output is correct
17 Correct 379 ms 34540 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5172 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5300 KB Output is correct
5 Correct 6 ms 5076 KB Output is correct
6 Correct 6 ms 5460 KB Output is correct
7 Correct 4 ms 5204 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 4 ms 5168 KB Output is correct
11 Correct 4 ms 5096 KB Output is correct
12 Correct 4 ms 5204 KB Output is correct
13 Correct 4 ms 5428 KB Output is correct
14 Correct 4 ms 5168 KB Output is correct
15 Correct 4 ms 5168 KB Output is correct
16 Correct 4 ms 5204 KB Output is correct
17 Correct 4 ms 5300 KB Output is correct
18 Correct 4 ms 5204 KB Output is correct
19 Correct 5 ms 5076 KB Output is correct
20 Correct 5 ms 5460 KB Output is correct
21 Correct 5 ms 5236 KB Output is correct
22 Correct 5 ms 5180 KB Output is correct
23 Correct 5 ms 5224 KB Output is correct
24 Correct 4 ms 5204 KB Output is correct
25 Correct 4 ms 5096 KB Output is correct
26 Correct 4 ms 5108 KB Output is correct
27 Correct 4 ms 5296 KB Output is correct
28 Correct 4 ms 5332 KB Output is correct
29 Correct 4 ms 5204 KB Output is correct
30 Correct 4 ms 5120 KB Output is correct
31 Correct 4 ms 5296 KB Output is correct
32 Correct 5 ms 5232 KB Output is correct
33 Correct 192 ms 10776 KB Output is correct
34 Correct 188 ms 28872 KB Output is correct
35 Correct 23 ms 8780 KB Output is correct
36 Correct 317 ms 17856 KB Output is correct
37 Correct 393 ms 46680 KB Output is correct
38 Correct 392 ms 32008 KB Output is correct
39 Correct 289 ms 18220 KB Output is correct
40 Correct 361 ms 20752 KB Output is correct
41 Correct 280 ms 19956 KB Output is correct
42 Correct 289 ms 19824 KB Output is correct
43 Correct 210 ms 21656 KB Output is correct
44 Correct 334 ms 35692 KB Output is correct
45 Correct 349 ms 32336 KB Output is correct
46 Correct 295 ms 31360 KB Output is correct
47 Correct 179 ms 21740 KB Output is correct
48 Correct 371 ms 37844 KB Output is correct
49 Correct 294 ms 32688 KB Output is correct
50 Correct 265 ms 13524 KB Output is correct
51 Correct 341 ms 47168 KB Output is correct
52 Correct 32 ms 9484 KB Output is correct
53 Correct 320 ms 19520 KB Output is correct
54 Correct 401 ms 49176 KB Output is correct
55 Correct 347 ms 33924 KB Output is correct
56 Correct 327 ms 19652 KB Output is correct
57 Correct 319 ms 25584 KB Output is correct
58 Correct 364 ms 23640 KB Output is correct
59 Correct 312 ms 21868 KB Output is correct
60 Correct 319 ms 21232 KB Output is correct
61 Correct 366 ms 43208 KB Output is correct
62 Correct 386 ms 32392 KB Output is correct
63 Correct 362 ms 32736 KB Output is correct
64 Correct 208 ms 22680 KB Output is correct
65 Correct 286 ms 40188 KB Output is correct
66 Correct 379 ms 34540 KB Output is correct
67 Correct 22 ms 6868 KB Output is correct
68 Correct 107 ms 23716 KB Output is correct
69 Correct 180 ms 22344 KB Output is correct
70 Correct 326 ms 17876 KB Output is correct
71 Correct 407 ms 46732 KB Output is correct
72 Correct 346 ms 32144 KB Output is correct
73 Correct 350 ms 18120 KB Output is correct
74 Correct 341 ms 23488 KB Output is correct
75 Correct 317 ms 20556 KB Output is correct
76 Correct 343 ms 20184 KB Output is correct
77 Correct 226 ms 19636 KB Output is correct
78 Correct 410 ms 38828 KB Output is correct
79 Correct 329 ms 35704 KB Output is correct
80 Correct 403 ms 29840 KB Output is correct
81 Correct 162 ms 21472 KB Output is correct
82 Correct 297 ms 37696 KB Output is correct
83 Correct 295 ms 32568 KB Output is correct
84 Correct 291 ms 18120 KB Output is correct
85 Correct 410 ms 47364 KB Output is correct
86 Correct 358 ms 32496 KB Output is correct
87 Correct 337 ms 18204 KB Output is correct
88 Correct 316 ms 24264 KB Output is correct
89 Correct 393 ms 21432 KB Output is correct
90 Correct 319 ms 20524 KB Output is correct
91 Correct 287 ms 20084 KB Output is correct
92 Correct 383 ms 46348 KB Output is correct
93 Correct 394 ms 28696 KB Output is correct
94 Correct 315 ms 25780 KB Output is correct
95 Correct 198 ms 22016 KB Output is correct
96 Correct 294 ms 38356 KB Output is correct
97 Correct 310 ms 33228 KB Output is correct
98 Correct 408 ms 19484 KB Output is correct
99 Correct 359 ms 47760 KB Output is correct
100 Correct 411 ms 33648 KB Output is correct
101 Correct 265 ms 19196 KB Output is correct
102 Correct 334 ms 23548 KB Output is correct
103 Correct 409 ms 21724 KB Output is correct
104 Correct 309 ms 21148 KB Output is correct
105 Correct 247 ms 20548 KB Output is correct
106 Correct 346 ms 35544 KB Output is correct
107 Correct 362 ms 36248 KB Output is correct
108 Correct 314 ms 28456 KB Output is correct
109 Correct 176 ms 22536 KB Output is correct
110 Correct 324 ms 39104 KB Output is correct
111 Correct 372 ms 34088 KB Output is correct