Submission #1092544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092544		onbert	Mergers (JOI19_mergers)	C++17	100 / 100	938 ms	234324 KiB

mergers

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5 + 5, maxk = 5e5+5, lg = 20;
int n, k;
vector<int> ADJ[maxn];
int A[maxn];

int SZ[maxn], FA[maxn], newid[maxn], lim[maxn], cnt = 0;
bool cmp(int x, int y) {
    return SZ[x] > SZ[y];
}
void DFS0(int u) {
    SZ[u] = 1;
    for (int v:ADJ[u]) {
        FA[v] = u;
        ADJ[v].erase(find(ADJ[v].begin(), ADJ[v].end(), u));
        DFS0(v);
        SZ[u] += SZ[v];
    }
    sort(ADJ[u].begin(), ADJ[u].end(), cmp);
}
void DFS1(int u) {
    cnt++;
    newid[u] = cnt;
    for (int v:ADJ[u]) DFS1(v);
    lim[newid[u]] = cnt;
}

vector<int> adj[maxn];
int fa[maxn], sz[maxn];
vector<int> mem[maxk];
int a[maxn];

int st[maxn][lg];
void dfs0(int u) {
    for (int i=1;i<lg;i++) {
        if (!st[u][i-1] || !st[st[u][i-1]][i-1]) break;
        st[u][i] = st[st[u][i-1]][i-1];
    }
    for (int v:adj[u]) {
        st[v][0] = u;
        dfs0(v);
    }
}

int psum[maxn];
int lca(int u, int c) {
    int l = mem[c][0], r = mem[c].back();
    for (int i=lg-1;i>=0;i--) if (st[u][i]) {
        int v = st[u][i];
        if (!(v<=l && r<=lim[v])) u = v;
    }
    // cout << c << " " << l << " " << r << endl;
    if (!(u<=l && r<=lim[u])) u = fa[u];
    return u;
}

bool sep[maxn];
bool sepleaf[maxn];

int sum[maxn];
int dead = 0, ans = 0;
bool frst = false;

void dfs1(int u, int minus) {
    // cout << u << " " << minus << endl;
    if (minus==0 && sep[u]) frst = true;
    if (sum[lim[u]] - sum[u-1] - minus == 1 && sep[u]) dead++;
    if (adj[u].size()==0) return;
    vector<pair<int,int>> vec;
    for (int v:adj[u]) {
        vec.push_back({sum[lim[v]] - sum[v-1], v});
    }
    sort(vec.begin(), vec.end());
    int l = 0, r = 1e18;
    while (l<r) {
        int mid = (l+r)/2, used = 0;
        for (auto [x, y]:vec) used += max(x - mid, (int)0);
        if (used <= minus) r = mid;
        else l = mid+1;
    }
    for (auto &[x, y]:vec) x = min(x, l);
    int total = sum[lim[u]] - sum[u] - minus;
    if (vec[0].first <= (total+1)/2) {
        ans += (total+1)/2;
        return;
    }
    int rest = total - vec[0].first;
    vec[0].first -= rest;
    int v = vec[0].second;
    ans += rest;
    dfs1(v, sum[lim[v]] - sum[v-1] - vec[0].first);
}


signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for (int i=1;i<=n-1;i++) {
        int u, v;
        cin >> u >> v;
        ADJ[u].push_back(v), ADJ[v].push_back(u);
    }
    for (int i=1;i<=n;i++) cin >> A[i];
    DFS0(1);
    DFS1(1);
    // for (int i=1;i<=n;i++) cout << newid[i] << " "; cout << endl;
    // for (int i=1;i<=n;i++) cout << lim[i] << " "; cout << endl;
    for (int i=1;i<=n;i++) {
        for (int j:ADJ[i]) adj[newid[i]].push_back(newid[j]);
        if (i!=1) fa[newid[i]] = newid[FA[i]];
        else fa[i] = 0;
        sz[newid[i]] = SZ[i];
    }
    for (int i=1;i<=n;i++) {
        a[newid[i]] = A[i];
        mem[A[i]].push_back(newid[i]);
    }
    dfs0(1);
    for (int i=1;i<=k;i++) {
        sort(mem[i].begin(), mem[i].end());
        psum[lca(mem[i][0], i)] += mem[i].size();
    }
    for (int i=1;i<=n;i++) psum[i] += psum[i-1];

    for (int i=2;i<=n;i++) {
        sep[i] = (psum[lim[i]] - psum[i-1] == lim[i] - i + 1);
        // cout << psum[lim[i]] - psum[i-1] << " " << lim[i] - i + 1 << endl;
    }
    // for (int i=1;i<=n;i++) cout << sep[i]; cout << endl;
    
    for (int i=1;i<=n;i++) sum[i] = sum[i-1] + sep[i];

    for (int i=1;i<=n;i++) sepleaf[i] = (sep[i] && sum[lim[i]] - sum[i-1] == 1);

    bool add = false;
    for (int i=2;i<=n;i++) if (sum[lim[i]] - sum[i-1] == sum[n] && sep[i] && !sepleaf[i]) add = true;

    int ans = 0;
    for (int i=1;i<=n;i++) ans += sepleaf[i];
    if (ans%2==1) cout << (ans+1)/2 << endl;
    else cout << ans/2 + add << endl;
    // if (sum[n]==0) {
    //     cout << 0 << endl;
    //     return 0;
    // }
    // dfs1(1, 0);
    // // assert(dead<=1);
    // cout << ans + (dead+1)/2 << endl;
}

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