Submission #604398

#	Time	Username	Problem	Language	Result	Execution time	Memory
604398		talant117408	Mergers (JOI19_mergers)	C++17	0 / 100	276 ms	55748 KiB

mergers

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'
#define PI                  2*acos(0.0)

const int N = 5e5+7;
vector <int> graph[N], comps_graph[N];
int color[N], states[N], comp[N], num;
int tin[N], tout[N], timer;
int color_lca[N];
int up[N][20];
int n;
int heavy[N], head[N], pos[N];
map <pii, bool> separators;

// LCA
bool upper(int a, int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int get_lca(int a, int b) {
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;
    for (int i = 19; i >= 0; i--) {
        if (!upper(up[a][i], b)) {
            a = up[a][i];
        }
    }
    return up[a][0];
}

// HLD
int dfs(int v, int p) {
    heavy[v] = -1;
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i < 20; i++) {
        up[v][i] = up[up[v][i-1]][i-1];
    }
    int saizu = 1, mx_saizu = 0;
    
    for (auto to : graph[v]) {
        if (to == p) continue;
        auto res = dfs(to, v);
        saizu += res;
        if (res > mx_saizu) {
            mx_saizu = res;
            heavy[v] = to;
        }
    }
    tout[v] = ++timer;
    return saizu;
}

void decompose(int v, int h) {
    pos[v] = ++timer;
    head[v] = h;
    if (heavy[v] != -1) {
        decompose(heavy[v], h);
    }
    for (auto to : graph[v]) {
        if (to != up[v][0] && to != heavy[v]) {
            decompose(to, to);
        }
    }
}

int tree[N*4], lz[N*4];

void push(int v, int l, int r) {
    if (lz[v] != 0) {
        tree[v] += (r - l + 1) * lz[v];
        if (l != r) {
            lz[v * 2] += lz[v];
            lz[v * 2 + 1] += lz[v];
        }
        lz[v] = 0;
    }
}

void update(int v, int l, int r, int ql, int qr, int val) {
    push(v, l, r);
    if (ql > r || l > qr) return ;
    if (ql <= l && r <= qr) {
        lz[v] += val;
        push(v, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    update(v*2, l, mid, ql, qr, val);
    update(v*2+1, mid+1, r, ql, qr, val);
    tree[v] = tree[v*2] + tree[v*2+1];
}

int get(int v, int l, int r, int ql, int qr) {
    push(v, l, r);
    if (ql > r || l > qr) return 0;
    if (ql <= l && r <= qr) return tree[v];
    int mid = (l + r) >> 1;
    return get(v*2, l, mid, ql, qr) + get(v*2+1, mid+1, r, ql, qr);
}

void hld_update(int v, int origin) {
    for (; head[v] != head[origin]; v = up[head[v]][0]) {
        update(1, 1, n, pos[head[v]], pos[v], 1);
    }
    update(1, 1, n, pos[origin], pos[v], 1);
    update(1, 1, n, pos[origin], pos[origin], -1);
}

void find_states(int v, int p) {
    if (get(1, 1, n, pos[v], pos[v]) == 0) {
        separators[mp(min(v, p), max(v, p))] = 1;
    }
    for (auto to : graph[v]) {
        if (to == p) continue;
        find_states(to, v);
    }
}

void find_comps(int v, int p) {
    comp[v] = num;
    for (auto to : graph[v]) {
        if (to == p || separators[mp(min(v, to), max(v, to))]) continue;
        find_comps(to, v);
    }
}

void solve(int test) {
    int k;
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].pb(b);
        graph[b].pb(a);
    }
    for (int i = 1; i <= n; i++) {
        cin >> color[i];
        states[color[i]]++;
    }
    dfs(1, 1);
    timer = 0;
    decompose(1, 1);
    
    vector <pii> LCAS[k + 1];
    for (int i = 1; i <= n; i++) {
        LCAS[color[i]].pb(mp(tin[i], i));
    }
    for (int i = 1; i <= k; i++) {
        sort(all(LCAS[i]));
        int tmp = LCAS[i][0].second;
        for (int j = 1; j < sz(LCAS[i]); j++) {
            tmp = get_lca(tmp, LCAS[i][j].second);
        }
        color_lca[i] = tmp;
    }
    
    for (int i = 1; i <= n; i++) {
        hld_update(i, color_lca[color[i]]);
    }
    
    find_states(1, 1);
    for (int i = 1; i <= n; i++) {
        if (!comp[i]) {
            num++;
            find_comps(i, i);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (auto to : graph[i]) {
            if (comp[i] != comp[to]) {
                comps_graph[comp[i]].pb(comp[to]);
            }
        }
    }
    int ans = -1;
    for (int i = 1; i <= num; i++) {
        if (sz(comps_graph[i]) == 1) ans++;
    }
    cout << (ans + 1) / 2 << endl;
}  

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    for (int i = 1; i <= t; i++) {
        solve(i);
    }
    
    return 0;
}
/*
11 6
1 2
2 4
4 3
2 5
5 6
2 8
8 7
7 9
7 10 
10 11
5 6 4 3 4 5 2 1 2 1 2
*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30