oj.uz

답안 #532175

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
532175 2022-03-02T08:36:58 Z syl123456 Unique Cities (JOI19_ho_t5) C++17
100 / 100
 314 ms 35168 KB 
#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
template<typename T1>
void Debug(bool _split, T1 i) {
    if (_split)
        cerr << ", ";
    cerr << i;
}
template<typename T1, typename ...T2>
void Debug(bool _split, T1 i, T2 ...j) {
    if (_split)
        cerr << ", ";
    cerr << i;
    Debug(true, j...);
}
#define debug(args...) cout << "Line" << __LINE__ << " : [" << #args << "] is [", Debug(false, args), cerr << "]" << endl;
 
typedef pair<int, int> pi;
typedef long long ll;
 
const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f;

const int N = 2e5;
 
vector<int> g[N];
int pa[N], c[N], at[N], cnt[N], ans[N];
pair<pi, pi> mx[N];
vector<pi> vv;

int now;

pi dfs1(int i, int p) {
    pa[i] = p;
    pi res(0, i);
    for (int j : g[i])
        if (j != p) {
            pi tmp = dfs1(j, i);
            ++tmp.first;
            res = max(res, tmp);
        }
    return res;
}
 
int dfs2(int i, int p, int _v) {
    mx[i].first = mx[i].second = pi(0, i);
    for (int j : g[i])
        if (j != p) {
            pi tmp(dfs2(j, i, _v - 1) + 1, j);
            if (tmp.first > mx[i].first.first)
                mx[i].second = mx[i].first, mx[i].first = tmp;
            else if (tmp.first > mx[i].second.first)
                mx[i].second = tmp;
        }
    return mx[i].first.first;
}
 
void dfs3(int i, int p, int _v) {
    if (at[_v] == -2)
        at[_v] = c[i];
    else
        at[_v] = -1;
    for (int j : g[i])
        if (j != p)
            dfs3(j, i, _v + 1);
}

void add(int x, int y) {
    vv.emplace_back(x, y);
    if (!cnt[y])
        ++now;
    ++cnt[y];
}

void del(int x = inf, int y = -1) {
    if (~y && (vv.empty() || vv.back() != pi(x, y)))
        return;
    y = vv.back().second;
    vv.pop_back();
    --cnt[y];
    if (!cnt[y])
        --now;
}
 
void dfs4(int i, int p, int _v) {
    int tmp;

    if (mx[i].first.second != i) {
        if (mx[i].second.first > 0)
            tmp = _v + mx[i].second.first;
        else
            tmp = _v;
        
        while (vv.back().first <= tmp)
            del();

        add(_v, c[i]);
        
        dfs4(mx[i].first.second, i, _v - 1);
    }

    if (mx[i].first.first > 0)
        tmp = _v + mx[i].first.first;
    else
        tmp = _v;

    while (vv.back().first <= tmp)
        del();

    ans[i] = now;

    for (int j : g[i])
        if (j != p && j != mx[i].first.second) {
            while (vv.back().first <= tmp)
                del();
            add(_v, c[i]);
            dfs4(j, i, _v - 1);
        }
}
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, _;
    cin >> n >> _;
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        g[x].push_back(y), g[y].push_back(x);
    }
    for (int i = 0; i < n; ++i)
        cin >> c[i], --c[i];
    int x = dfs1(0, -1).second;
    int y = dfs1(x, -1).second;
    vector<int> dm;
    for (int i = y; ~i; i = pa[i])
        dm.push_back(i);

    x = dm.size() - 1 >> 1;//2k -> k-1, 2k+1 -> k
    dfs2(dm[x], dm[x + 1], 0);
    fill(at, at + n, -2);
    dfs3(dm[x + 1], dm[x], 1);
    fill(cnt, cnt + n, 0);
    now = 0;
    vv.emplace_back(inf, -1);
    for (int i = n - 1; i; --i)
        if (at[i] >= 0) {
            add(i, at[i]);
        }
    dfs4(dm[x], dm[x + 1], 0);
 
    x = dm.size() >> 1;//2k -> k, 2k+1 -> k
    dfs2(dm[x], dm[x - 1], 0);
    fill(at, at + n, -2);
    dfs3(dm[x - 1], dm[x], 1);
    fill(cnt, cnt + n, 0);
    now = 0;
    vv.clear();
    vv.emplace_back(inf, -1);
    for (int i = n - 1; i; --i)
        if (at[i] >= 0) {
            add(i, at[i]);
        }
    dfs4(dm[x], dm[x - 1], 0);
 
    for (int i = 0; i < n; ++i)
        cout << ans[i] << '\n';
}

Compilation message

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:140:19: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  140 |     x = dm.size() - 1 >> 1;//2k -> k-1, 2k+1 -> k
      |         ~~~~~~~~~~^~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 5080 KB Output is correct
3 Correct 3 ms 5132 KB Output is correct
4 Correct 4 ms 5152 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 4 ms 5288 KB Output is correct
7 Correct 4 ms 5196 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 4 ms 5152 KB Output is correct
11 Correct 4 ms 5196 KB Output is correct
12 Correct 4 ms 5152 KB Output is correct
13 Correct 5 ms 5284 KB Output is correct
14 Correct 4 ms 5152 KB Output is correct
15 Correct 6 ms 5260 KB Output is correct
16 Correct 5 ms 5196 KB Output is correct
17 Correct 4 ms 5284 KB Output is correct
18 Correct 4 ms 5196 KB Output is correct
19 Correct 4 ms 5196 KB Output is correct
20 Correct 4 ms 5324 KB Output is correct
21 Correct 4 ms 5196 KB Output is correct
22 Correct 4 ms 5196 KB Output is correct
23 Correct 4 ms 5196 KB Output is correct
24 Correct 5 ms 5208 KB Output is correct
25 Correct 4 ms 5196 KB Output is correct
26 Correct 4 ms 5196 KB Output is correct
27 Correct 4 ms 5324 KB Output is correct
28 Correct 4 ms 5196 KB Output is correct
29 Correct 5 ms 5192 KB Output is correct
30 Correct 4 ms 5156 KB Output is correct
31 Correct 5 ms 5284 KB Output is correct
32 Correct 5 ms 5188 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 12932 KB Output is correct
2 Correct 140 ms 20592 KB Output is correct
3 Correct 25 ms 8136 KB Output is correct
4 Correct 239 ms 21864 KB Output is correct
5 Correct 296 ms 33484 KB Output is correct
6 Correct 290 ms 27504 KB Output is correct
7 Correct 200 ms 21788 KB Output is correct
8 Correct 291 ms 22940 KB Output is correct
9 Correct 237 ms 22440 KB Output is correct
10 Correct 227 ms 22416 KB Output is correct
11 Correct 129 ms 22432 KB Output is correct
12 Correct 263 ms 28684 KB Output is correct
13 Correct 234 ms 27396 KB Output is correct
14 Correct 240 ms 26820 KB Output is correct
15 Correct 132 ms 22260 KB Output is correct
16 Correct 255 ms 30048 KB Output is correct
17 Correct 253 ms 27328 KB Output is correct

Subtask #3
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 15940 KB Output is correct
2 Correct 272 ms 31236 KB Output is correct
3 Correct 24 ms 8656 KB Output is correct
4 Correct 234 ms 22588 KB Output is correct
5 Correct 295 ms 35168 KB Output is correct
6 Correct 287 ms 28360 KB Output is correct
7 Correct 226 ms 22644 KB Output is correct
8 Correct 242 ms 25156 KB Output is correct
9 Correct 263 ms 24324 KB Output is correct
10 Correct 242 ms 23528 KB Output is correct
11 Correct 223 ms 23028 KB Output is correct
12 Correct 305 ms 32708 KB Output is correct
13 Correct 252 ms 27880 KB Output is correct
14 Correct 255 ms 27720 KB Output is correct
15 Correct 127 ms 23292 KB Output is correct
16 Correct 257 ms 31288 KB Output is correct
17 Correct 267 ms 28560 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 5080 KB Output is correct
3 Correct 3 ms 5132 KB Output is correct
4 Correct 4 ms 5152 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 4 ms 5288 KB Output is correct
7 Correct 4 ms 5196 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 4 ms 5152 KB Output is correct
11 Correct 4 ms 5196 KB Output is correct
12 Correct 4 ms 5152 KB Output is correct
13 Correct 5 ms 5284 KB Output is correct
14 Correct 4 ms 5152 KB Output is correct
15 Correct 6 ms 5260 KB Output is correct
16 Correct 5 ms 5196 KB Output is correct
17 Correct 4 ms 5284 KB Output is correct
18 Correct 4 ms 5196 KB Output is correct
19 Correct 4 ms 5196 KB Output is correct
20 Correct 4 ms 5324 KB Output is correct
21 Correct 4 ms 5196 KB Output is correct
22 Correct 4 ms 5196 KB Output is correct
23 Correct 4 ms 5196 KB Output is correct
24 Correct 5 ms 5208 KB Output is correct
25 Correct 4 ms 5196 KB Output is correct
26 Correct 4 ms 5196 KB Output is correct
27 Correct 4 ms 5324 KB Output is correct
28 Correct 4 ms 5196 KB Output is correct
29 Correct 5 ms 5192 KB Output is correct
30 Correct 4 ms 5156 KB Output is correct
31 Correct 5 ms 5284 KB Output is correct
32 Correct 5 ms 5188 KB Output is correct
33 Correct 95 ms 12932 KB Output is correct
34 Correct 140 ms 20592 KB Output is correct
35 Correct 25 ms 8136 KB Output is correct
36 Correct 239 ms 21864 KB Output is correct
37 Correct 296 ms 33484 KB Output is correct
38 Correct 290 ms 27504 KB Output is correct
39 Correct 200 ms 21788 KB Output is correct
40 Correct 291 ms 22940 KB Output is correct
41 Correct 237 ms 22440 KB Output is correct
42 Correct 227 ms 22416 KB Output is correct
43 Correct 129 ms 22432 KB Output is correct
44 Correct 263 ms 28684 KB Output is correct
45 Correct 234 ms 27396 KB Output is correct
46 Correct 240 ms 26820 KB Output is correct
47 Correct 132 ms 22260 KB Output is correct
48 Correct 255 ms 30048 KB Output is correct
49 Correct 253 ms 27328 KB Output is correct
50 Correct 152 ms 15940 KB Output is correct
51 Correct 272 ms 31236 KB Output is correct
52 Correct 24 ms 8656 KB Output is correct
53 Correct 234 ms 22588 KB Output is correct
54 Correct 295 ms 35168 KB Output is correct
55 Correct 287 ms 28360 KB Output is correct
56 Correct 226 ms 22644 KB Output is correct
57 Correct 242 ms 25156 KB Output is correct
58 Correct 263 ms 24324 KB Output is correct
59 Correct 242 ms 23528 KB Output is correct
60 Correct 223 ms 23028 KB Output is correct
61 Correct 305 ms 32708 KB Output is correct
62 Correct 252 ms 27880 KB Output is correct
63 Correct 255 ms 27720 KB Output is correct
64 Correct 127 ms 23292 KB Output is correct
65 Correct 257 ms 31288 KB Output is correct
66 Correct 267 ms 28560 KB Output is correct
67 Correct 22 ms 7248 KB Output is correct
68 Correct 95 ms 17960 KB Output is correct
69 Correct 153 ms 19308 KB Output is correct
70 Correct 233 ms 21832 KB Output is correct
71 Correct 271 ms 33424 KB Output is correct
72 Correct 288 ms 27236 KB Output is correct
73 Correct 204 ms 21704 KB Output is correct
74 Correct 238 ms 23704 KB Output is correct
75 Correct 229 ms 22868 KB Output is correct
76 Correct 231 ms 22628 KB Output is correct
77 Correct 199 ms 22012 KB Output is correct
78 Correct 273 ms 29908 KB Output is correct
79 Correct 239 ms 28940 KB Output is correct
80 Correct 250 ms 26328 KB Output is correct
81 Correct 123 ms 22072 KB Output is correct
82 Correct 238 ms 29732 KB Output is correct
83 Correct 267 ms 27276 KB Output is correct
84 Correct 260 ms 21924 KB Output is correct
85 Correct 281 ms 34064 KB Output is correct
86 Correct 292 ms 27728 KB Output is correct
87 Correct 212 ms 21960 KB Output is correct
88 Correct 238 ms 24392 KB Output is correct
89 Correct 232 ms 23448 KB Output is correct
90 Correct 254 ms 23032 KB Output is correct
91 Correct 157 ms 22344 KB Output is correct
92 Correct 278 ms 33712 KB Output is correct
93 Correct 244 ms 26268 KB Output is correct
94 Correct 251 ms 24988 KB Output is correct
95 Correct 129 ms 22560 KB Output is correct
96 Correct 243 ms 30336 KB Output is correct
97 Correct 264 ms 27936 KB Output is correct
98 Correct 250 ms 22588 KB Output is correct
99 Correct 314 ms 34728 KB Output is correct
100 Correct 301 ms 28348 KB Output is correct
101 Correct 271 ms 22468 KB Output is correct
102 Correct 254 ms 24420 KB Output is correct
103 Correct 241 ms 23760 KB Output is correct
104 Correct 231 ms 23368 KB Output is correct
105 Correct 193 ms 22792 KB Output is correct
106 Correct 272 ms 29220 KB Output is correct
107 Correct 268 ms 29784 KB Output is correct
108 Correct 271 ms 26096 KB Output is correct
109 Correct 127 ms 23220 KB Output is correct
110 Correct 252 ms 31092 KB Output is correct
111 Correct 265 ms 28456 KB Output is correct