oj.uz

답안 #1092527

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1092527 2024-09-24T10:20:00 Z onbert Mergers (JOI19_mergers) C++17
0 / 100
 102 ms 72020 KB 
#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;

void dfs1(int u, int minus) {
    if (sum[lim[u]] - sum[u-1] - minus <= 0) return;
    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] - 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<=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);
    for (int i=1;i<=n;i++) sum[i] = sum[i-1] + sepleaf[i];
    dfs1(1, 0);
    assert(dead<=1);
    cout << ans + (dead+1)/2 << endl;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 35672 KB Output is correct
2 Correct 17 ms 35676 KB Output is correct
3 Correct 17 ms 35676 KB Output is correct
4 Correct 16 ms 35676 KB Output is correct
5 Correct 16 ms 35704 KB Output is correct
6 Correct 17 ms 35704 KB Output is correct
7 Correct 17 ms 35732 KB Output is correct
8 Correct 20 ms 35676 KB Output is correct
9 Correct 17 ms 35676 KB Output is correct
10 Correct 17 ms 35676 KB Output is correct
11 Correct 16 ms 35672 KB Output is correct
12 Correct 17 ms 35676 KB Output is correct
13 Correct 21 ms 35676 KB Output is correct
14 Correct 17 ms 35676 KB Output is correct
15 Correct 17 ms 35704 KB Output is correct
16 Runtime error 45 ms 72020 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 35672 KB Output is correct
2 Correct 17 ms 35676 KB Output is correct
3 Correct 17 ms 35676 KB Output is correct
4 Correct 16 ms 35676 KB Output is correct
5 Correct 16 ms 35704 KB Output is correct
6 Correct 17 ms 35704 KB Output is correct
7 Correct 17 ms 35732 KB Output is correct
8 Correct 20 ms 35676 KB Output is correct
9 Correct 17 ms 35676 KB Output is correct
10 Correct 17 ms 35676 KB Output is correct
11 Correct 16 ms 35672 KB Output is correct
12 Correct 17 ms 35676 KB Output is correct
13 Correct 21 ms 35676 KB Output is correct
14 Correct 17 ms 35676 KB Output is correct
15 Correct 17 ms 35704 KB Output is correct
16 Runtime error 45 ms 72020 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 35672 KB Output is correct
2 Correct 17 ms 35676 KB Output is correct
3 Correct 17 ms 35676 KB Output is correct
4 Correct 16 ms 35676 KB Output is correct
5 Correct 16 ms 35704 KB Output is correct
6 Correct 17 ms 35704 KB Output is correct
7 Correct 17 ms 35732 KB Output is correct
8 Correct 20 ms 35676 KB Output is correct
9 Correct 17 ms 35676 KB Output is correct
10 Correct 17 ms 35676 KB Output is correct
11 Correct 16 ms 35672 KB Output is correct
12 Correct 17 ms 35676 KB Output is correct
13 Correct 21 ms 35676 KB Output is correct
14 Correct 17 ms 35676 KB Output is correct
15 Correct 17 ms 35704 KB Output is correct
16 Runtime error 45 ms 72020 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 66632 KB Output is correct
2 Correct 92 ms 71112 KB Output is correct
3 Correct 19 ms 36696 KB Output is correct
4 Correct 18 ms 36696 KB Output is correct
5 Correct 17 ms 35676 KB Output is correct
6 Correct 17 ms 35676 KB Output is correct
7 Correct 18 ms 36700 KB Output is correct
8 Correct 102 ms 68436 KB Output is correct
9 Incorrect 18 ms 36696 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 35672 KB Output is correct
2 Correct 17 ms 35676 KB Output is correct
3 Correct 17 ms 35676 KB Output is correct
4 Correct 16 ms 35676 KB Output is correct
5 Correct 16 ms 35704 KB Output is correct
6 Correct 17 ms 35704 KB Output is correct
7 Correct 17 ms 35732 KB Output is correct
8 Correct 20 ms 35676 KB Output is correct
9 Correct 17 ms 35676 KB Output is correct
10 Correct 17 ms 35676 KB Output is correct
11 Correct 16 ms 35672 KB Output is correct
12 Correct 17 ms 35676 KB Output is correct
13 Correct 21 ms 35676 KB Output is correct
14 Correct 17 ms 35676 KB Output is correct
15 Correct 17 ms 35704 KB Output is correct
16 Runtime error 45 ms 72020 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -