oj.uz

Submission #1092520

# Submission time Handle Problem Language Result Execution time Memory
1092520 2024-09-24T10:08:53 Z onbert Mergers (JOI19_mergers) C++17
0 / 100
 92 ms 70188 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5 + 5, maxk = 5e5+5, lg = 19;
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;

void dfs1(int u, int minus) {
    if (minus==0 && 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-1] - minus;
    if (vec[0].first <= (total+1)/2) {
        ans += (total+1)/2;
        return;
    }
    int rest = total - vec[0].first;
    int v = vec[0].second;
    ans += rest;
    dfs1(v, rest);
}


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<=n;i++) {
    //     for (int j=0;j<lg;j++) if (st[i][j]) cout << st[i][j] << " ";
    //     cout << endl;
    // }
    for (int i=1;i<=k;i++) {
        sort(mem[i].begin(), mem[i].end());
        psum[lca(mem[i][0], i)] += mem[i].size();
        // cout << i << " " << lca(mem[i][0], i) << endl;
    }
    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);
    for (int i=1;i<=n;i++) sum[i] = sum[i-1] + sepleaf[i];
    dfs1(1, 0);
    cout << ans + (dead+1)/2 << endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35676 KB Output is correct
2 Correct 17 ms 35560 KB Output is correct
3 Correct 17 ms 35700 KB Output is correct
4 Correct 16 ms 35648 KB Output is correct
5 Correct 17 ms 35676 KB Output is correct
6 Correct 16 ms 35696 KB Output is correct
7 Correct 16 ms 35528 KB Output is correct
8 Correct 17 ms 35676 KB Output is correct
9 Correct 16 ms 35676 KB Output is correct
10 Correct 16 ms 35712 KB Output is correct
11 Correct 16 ms 35676 KB Output is correct
12 Correct 21 ms 35676 KB Output is correct
13 Correct 16 ms 35932 KB Output is correct
14 Correct 16 ms 35676 KB Output is correct
15 Correct 16 ms 35672 KB Output is correct
16 Correct 16 ms 35676 KB Output is correct
17 Correct 14 ms 35672 KB Output is correct
18 Correct 17 ms 35724 KB Output is correct
19 Correct 17 ms 35672 KB Output is correct
20 Incorrect 16 ms 35676 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35676 KB Output is correct
2 Correct 17 ms 35560 KB Output is correct
3 Correct 17 ms 35700 KB Output is correct
4 Correct 16 ms 35648 KB Output is correct
5 Correct 17 ms 35676 KB Output is correct
6 Correct 16 ms 35696 KB Output is correct
7 Correct 16 ms 35528 KB Output is correct
8 Correct 17 ms 35676 KB Output is correct
9 Correct 16 ms 35676 KB Output is correct
10 Correct 16 ms 35712 KB Output is correct
11 Correct 16 ms 35676 KB Output is correct
12 Correct 21 ms 35676 KB Output is correct
13 Correct 16 ms 35932 KB Output is correct
14 Correct 16 ms 35676 KB Output is correct
15 Correct 16 ms 35672 KB Output is correct
16 Correct 16 ms 35676 KB Output is correct
17 Correct 14 ms 35672 KB Output is correct
18 Correct 17 ms 35724 KB Output is correct
19 Correct 17 ms 35672 KB Output is correct
20 Incorrect 16 ms 35676 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35676 KB Output is correct
2 Correct 17 ms 35560 KB Output is correct
3 Correct 17 ms 35700 KB Output is correct
4 Correct 16 ms 35648 KB Output is correct
5 Correct 17 ms 35676 KB Output is correct
6 Correct 16 ms 35696 KB Output is correct
7 Correct 16 ms 35528 KB Output is correct
8 Correct 17 ms 35676 KB Output is correct
9 Correct 16 ms 35676 KB Output is correct
10 Correct 16 ms 35712 KB Output is correct
11 Correct 16 ms 35676 KB Output is correct
12 Correct 21 ms 35676 KB Output is correct
13 Correct 16 ms 35932 KB Output is correct
14 Correct 16 ms 35676 KB Output is correct
15 Correct 16 ms 35672 KB Output is correct
16 Correct 16 ms 35676 KB Output is correct
17 Correct 14 ms 35672 KB Output is correct
18 Correct 17 ms 35724 KB Output is correct
19 Correct 17 ms 35672 KB Output is correct
20 Incorrect 16 ms 35676 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 65868 KB Output is correct
2 Correct 89 ms 70188 KB Output is correct
3 Correct 18 ms 36700 KB Output is correct
4 Correct 20 ms 36572 KB Output is correct
5 Correct 16 ms 35672 KB Output is correct
6 Correct 17 ms 35676 KB Output is correct
7 Correct 17 ms 36444 KB Output is correct
8 Correct 92 ms 67812 KB Output is correct
9 Incorrect 17 ms 36696 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35676 KB Output is correct
2 Correct 17 ms 35560 KB Output is correct
3 Correct 17 ms 35700 KB Output is correct
4 Correct 16 ms 35648 KB Output is correct
5 Correct 17 ms 35676 KB Output is correct
6 Correct 16 ms 35696 KB Output is correct
7 Correct 16 ms 35528 KB Output is correct
8 Correct 17 ms 35676 KB Output is correct
9 Correct 16 ms 35676 KB Output is correct
10 Correct 16 ms 35712 KB Output is correct
11 Correct 16 ms 35676 KB Output is correct
12 Correct 21 ms 35676 KB Output is correct
13 Correct 16 ms 35932 KB Output is correct
14 Correct 16 ms 35676 KB Output is correct
15 Correct 16 ms 35672 KB Output is correct
16 Correct 16 ms 35676 KB Output is correct
17 Correct 14 ms 35672 KB Output is correct
18 Correct 17 ms 35724 KB Output is correct
19 Correct 17 ms 35672 KB Output is correct
20 Incorrect 16 ms 35676 KB Output isn't correct
21 Halted 0 ms 0 KB -