oj.uz

Submission #594169

# Submission time Handle Problem Language Result Execution time Memory
594169 2022-07-12T07:29:26 Z 이동현(#8435) Unique Cities (JOI19_ho_t5) C++17
4 / 100
 2000 ms 18056 KB 
#include <bits/stdc++.h>

using namespace std;

const int NS = (int)2e5 + 4;
int n, m;
vector<int> way[NS];
int col[NS];
vector<int> vc[NS];

void dfs(int x, int dis, int pr = -1){
    vc[dis].push_back(col[x]);
    for(auto&nxt:way[x]){
        if(nxt == pr){
            continue;
        }
        dfs(nxt, dis + 1, x);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i < n; ++i){
        int x, y; cin >> x >> y; --x, --y;
        way[x].push_back(y);
        way[y].push_back(x);
    }
    for(int i = 0; i < n; ++i){
        cin >> col[i];
    }
    for(int i = 0; i < n; ++i){
        dfs(i, 0);
        set<int> ans;
        for(int j = 1; j <= n; ++j){
            if((int)vc[j].size() == 1) ans.insert(vc[j][0]);
            vc[j].clear();
        }
        cout << (int)ans.size() << '\n';
    }
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9720 KB Output is correct
2 Correct 58 ms 9860 KB Output is correct
3 Correct 64 ms 9856 KB Output is correct
4 Correct 78 ms 10104 KB Output is correct
5 Correct 78 ms 9860 KB Output is correct
6 Correct 108 ms 9956 KB Output is correct
7 Correct 84 ms 9960 KB Output is correct
8 Correct 59 ms 9844 KB Output is correct
9 Correct 77 ms 9868 KB Output is correct
10 Correct 67 ms 9988 KB Output is correct
11 Correct 68 ms 9892 KB Output is correct
12 Correct 42 ms 9860 KB Output is correct
13 Correct 106 ms 9960 KB Output is correct
14 Correct 74 ms 10712 KB Output is correct
15 Correct 81 ms 10596 KB Output is correct
16 Correct 39 ms 9848 KB Output is correct
17 Correct 86 ms 12584 KB Output is correct
18 Correct 80 ms 10888 KB Output is correct
19 Correct 71 ms 9856 KB Output is correct
20 Correct 258 ms 10000 KB Output is correct
21 Correct 102 ms 10044 KB Output is correct
22 Correct 58 ms 9860 KB Output is correct
23 Correct 67 ms 9884 KB Output is correct
24 Correct 72 ms 9896 KB Output is correct
25 Correct 73 ms 9888 KB Output is correct
26 Correct 48 ms 9864 KB Output is correct
27 Correct 201 ms 9992 KB Output is correct
28 Correct 147 ms 12308 KB Output is correct
29 Correct 86 ms 10732 KB Output is correct
30 Correct 51 ms 9840 KB Output is correct
31 Correct 124 ms 12600 KB Output is correct
32 Correct 95 ms 10788 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 16088 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2066 ms 18056 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9720 KB Output is correct
2 Correct 58 ms 9860 KB Output is correct
3 Correct 64 ms 9856 KB Output is correct
4 Correct 78 ms 10104 KB Output is correct
5 Correct 78 ms 9860 KB Output is correct
6 Correct 108 ms 9956 KB Output is correct
7 Correct 84 ms 9960 KB Output is correct
8 Correct 59 ms 9844 KB Output is correct
9 Correct 77 ms 9868 KB Output is correct
10 Correct 67 ms 9988 KB Output is correct
11 Correct 68 ms 9892 KB Output is correct
12 Correct 42 ms 9860 KB Output is correct
13 Correct 106 ms 9960 KB Output is correct
14 Correct 74 ms 10712 KB Output is correct
15 Correct 81 ms 10596 KB Output is correct
16 Correct 39 ms 9848 KB Output is correct
17 Correct 86 ms 12584 KB Output is correct
18 Correct 80 ms 10888 KB Output is correct
19 Correct 71 ms 9856 KB Output is correct
20 Correct 258 ms 10000 KB Output is correct
21 Correct 102 ms 10044 KB Output is correct
22 Correct 58 ms 9860 KB Output is correct
23 Correct 67 ms 9884 KB Output is correct
24 Correct 72 ms 9896 KB Output is correct
25 Correct 73 ms 9888 KB Output is correct
26 Correct 48 ms 9864 KB Output is correct
27 Correct 201 ms 9992 KB Output is correct
28 Correct 147 ms 12308 KB Output is correct
29 Correct 86 ms 10732 KB Output is correct
30 Correct 51 ms 9840 KB Output is correct
31 Correct 124 ms 12600 KB Output is correct
32 Correct 95 ms 10788 KB Output is correct
33 Execution timed out 2059 ms 16088 KB Time limit exceeded
34 Halted 0 ms 0 KB -