oj.uz

Submission #447158

# Submission time Handle Problem Language Result Execution time Memory
447158 2021-07-24T19:27:52 Z aryan12 Mergers (JOI19_mergers) C++17
0 / 100
 89 ms 53872 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 5e5 + 5;
vector<int> g[N], states[N];
int depth[N];
int DP[20][N];
int par[N];

int Find(int x) {
    if(par[x] == x) {
        return x;
    }
    return par[x] = Find(par[x]);
}

void Unite(int a, int b) {
    a = Find(a), b = Find(b);
    if(depth[a] > depth[b]) {
        swap(a, b);
    }
    par[b] = a;
}

void dfs(int node, int parent) {
    DP[0][node] = parent;
    for(auto i: g[node]) {
        if(i == parent) {
            continue;
        }
        depth[i] = depth[node] + 1;
        dfs(i, node);
    }
}

int LCA(int x, int y) {
    if(depth[x] > depth[y]) {
        swap(x, y);
    }
    int diff = depth[y] - depth[x];
    for(int i = 19; i >= 0; i--) {
        if((1 << i) <= diff) {
            diff -= (1 << i);
            y = DP[i][y];
        }
    }
    if(x == y) {
        return x;
    }
    for(int i = 19; i >= 0; i--) {
        if(DP[i][x] != DP[i][y]) {
            x = DP[i][x];
            y = DP[i][y];
        }
    }
    return DP[0][x];
}

bool cmp(int a, int b) {
    return depth[a] > depth[b];
}

void Solve() {
    for(int i = 0; i < N; i++) {
        par[i] = i;
    }
    int n, k;
    cin >> n >> k;
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    depth[1] = 1;
    dfs(1, -1);
    for(int i = 1; i < 20; i++) {
        for(int j = 1; j <= n; j++) {
            if(DP[i - 1][j] == -1) {
                DP[i][j] = -1;
            }
            else {
                DP[i][j] = DP[i - 1][DP[i - 1][j]];
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        int cur_state;
        cin >> cur_state;
        states[cur_state].push_back(i);
    }
    for(int i = 1; i <= k; i++) {
        sort(states[i].begin(), states[i].end(), cmp);
        /*cout << "i = " << i << ", size = " << states[i].size() << "\n";
        for(int j = 0; j < states[i].size(); j++) {
            cout << states[i][j] << " ";
        }
        cout << "\n";*/
        int len = states[i].size();
        int node = states[i][0];
        for(int j = 1; j < len; j++) {
            int lca = LCA(node, states[i][j]);
            int cur_node = Find(node);
            while(depth[cur_node] > depth[lca]) {
                Unite(cur_node, DP[0][cur_node]);
                cur_node = Find(cur_node);
            }
            cur_node = Find(states[i][j]);
            while(depth[cur_node] > depth[lca]) {
                Unite(cur_node, DP[0][cur_node]);
                cur_node = Find(cur_node);
            }
            node = lca;
        }
    }
    int degree[n + 1];
    for(int i = 0; i <= n; i++) {
        degree[i] = 0;
    }
    for(int i = 1; i <= n; i++) {
        for(auto j: g[i]) {
            if(Find(j) != Find(i) && j != DP[0][i]) {
                degree[Find(i)]++;
                degree[Find(j)]++;
            }
        }
    }
    int ans = 0;
    /*for(int i = 1; i <= n; i++) {
        cout << degree[i] << " ";
    }
    cout << "\n";
    for(int i = 1; i <= n; i++) {
        cout << Find(i) << " ";
    }
    cout << "\n";*/
    for(int i = 1; i <= n; i++) {
        if(degree[i] == 1) {
            ans++;
        }
    }
    cout << ans / 2 << "\n";
}

int32_t main() {
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27852 KB Output is correct
2 Correct 16 ms 27828 KB Output is correct
3 Correct 15 ms 27948 KB Output is correct
4 Correct 15 ms 27852 KB Output is correct
5 Correct 15 ms 27852 KB Output is correct
6 Correct 15 ms 27852 KB Output is correct
7 Correct 15 ms 27880 KB Output is correct
8 Correct 15 ms 27852 KB Output is correct
9 Correct 16 ms 27844 KB Output is correct
10 Correct 16 ms 27852 KB Output is correct
11 Correct 15 ms 27848 KB Output is correct
12 Correct 15 ms 27792 KB Output is correct
13 Correct 15 ms 27848 KB Output is correct
14 Incorrect 15 ms 27828 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27852 KB Output is correct
2 Correct 16 ms 27828 KB Output is correct
3 Correct 15 ms 27948 KB Output is correct
4 Correct 15 ms 27852 KB Output is correct
5 Correct 15 ms 27852 KB Output is correct
6 Correct 15 ms 27852 KB Output is correct
7 Correct 15 ms 27880 KB Output is correct
8 Correct 15 ms 27852 KB Output is correct
9 Correct 16 ms 27844 KB Output is correct
10 Correct 16 ms 27852 KB Output is correct
11 Correct 15 ms 27848 KB Output is correct
12 Correct 15 ms 27792 KB Output is correct
13 Correct 15 ms 27848 KB Output is correct
14 Incorrect 15 ms 27828 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27852 KB Output is correct
2 Correct 16 ms 27828 KB Output is correct
3 Correct 15 ms 27948 KB Output is correct
4 Correct 15 ms 27852 KB Output is correct
5 Correct 15 ms 27852 KB Output is correct
6 Correct 15 ms 27852 KB Output is correct
7 Correct 15 ms 27880 KB Output is correct
8 Correct 15 ms 27852 KB Output is correct
9 Correct 16 ms 27844 KB Output is correct
10 Correct 16 ms 27852 KB Output is correct
11 Correct 15 ms 27848 KB Output is correct
12 Correct 15 ms 27792 KB Output is correct
13 Correct 15 ms 27848 KB Output is correct
14 Incorrect 15 ms 27828 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 51512 KB Output is correct
2 Incorrect 89 ms 53872 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27852 KB Output is correct
2 Correct 16 ms 27828 KB Output is correct
3 Correct 15 ms 27948 KB Output is correct
4 Correct 15 ms 27852 KB Output is correct
5 Correct 15 ms 27852 KB Output is correct
6 Correct 15 ms 27852 KB Output is correct
7 Correct 15 ms 27880 KB Output is correct
8 Correct 15 ms 27852 KB Output is correct
9 Correct 16 ms 27844 KB Output is correct
10 Correct 16 ms 27852 KB Output is correct
11 Correct 15 ms 27848 KB Output is correct
12 Correct 15 ms 27792 KB Output is correct
13 Correct 15 ms 27848 KB Output is correct
14 Incorrect 15 ms 27828 KB Output isn't correct
15 Halted 0 ms 0 KB -