oj.uz

Submission #627168

# Submission time Handle Problem Language Result Execution time Memory
627168 2022-08-12T10:11:06 Z MohamedFaresNebili Capital City (JOI20_capital_city) C++14
0 / 100
 185 ms 38172 KB 
#include <bits/stdc++.h>

            using namespace std;

            using ll = long long;
            using ld = long double;
            using pi = pair<pair<int, int>, pair<int, int>>;

            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound

            int N, K, res = 1e9 + 7, C[200005];
            int cur[200005], par[200005], sz[200005];
            bool used[200005], seen[200005];
            vector<int> adj[200005], S[200005];

            int dfs_size(int v, int p) {
                sz[v] = 1; cur[C[v]] = 0;
                for(auto u : adj[v]) {
                    if(u == p || seen[u]) continue;
                    sz[v] += dfs_size(u, v);
                }
                return sz[v];
            }
            int dfs_centroid(int v, int p, int _N) {
                for(auto u : adj[v]) {
                    if(u == p || seen[u]) continue;
                    if(sz[u] >= _N / 2) return dfs_centroid(u, v, _N);
                }
                return v;
            }
            void dfs(int v, int p) {
                par[v] = p; cur[C[v]]++; used[C[v]] = 0;
                for(auto u : adj[v]) {
                    if(u == p || seen[u]) continue;
                    dfs(u, v);
                }
            }
            void build(int v) {
                int _N = dfs_size(v, v);
                int centroid = dfs_centroid(v, v, _N);
                dfs(centroid, centroid); seen[centroid] = 1;
                int ans = 0;
                stack<int> st; st.push(C[centroid]);
                while(!st.empty()) {
                    int u = st.top(); st.pop();
                    if(used[u]) continue;
                    if(cur[u] != S[u].size()) { ans = 1e9 + 7; break; }
                    used[u] = 1; ans++;
                    for(auto e : S[u]) st.push(C[par[e]]);
                }
                res = min(res, ans - 1);
                for(auto u : adj[v]) {
                    if(seen[u]) continue;
                    build(u);
                }
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> K;
                for(int l = 0; l < N - 1; l++) {
                    int A, B; cin >> A >> B;
                    adj[A].push_back(B);
                    adj[B].push_back(A);
                }
                for(int l = 1; l <= N; l++)
                    cin >> C[l], S[C[l]].push_back(l);
                build(1); cout << res << "\n";
                return 0;
            }

Compilation message

capital_city.cpp: In function 'void build(int)':
capital_city.cpp:51:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |                     if(cur[u] != S[u].size()) { ans = 1e9 + 7; break; }
      |                        ~~~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9748 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 5 ms 9644 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Incorrect 5 ms 9684 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9748 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 5 ms 9644 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Incorrect 5 ms 9684 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 34148 KB Output is correct
2 Correct 91 ms 38172 KB Output is correct
3 Correct 185 ms 37588 KB Output is correct
4 Correct 103 ms 38108 KB Output is correct
5 Incorrect 174 ms 35064 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9748 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 6 ms 9684 KB Output is correct
5 Correct 5 ms 9644 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Incorrect 5 ms 9684 KB Output isn't correct
8 Halted 0 ms 0 KB -