oj.uz

Submission #1085447

# Submission time Handle Problem Language Result Execution time Memory
1085447 2024-09-08T09:09:13 Z underwaterkillerwhale Mergers (JOI19_mergers) C++17
0 / 100
 32 ms 17108 KB 
#include <bits/stdc++.h>
#define ll              long long
#define pii             pair<int,int>
#define pll             pair<ll,ll>
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
#define iter(id, v)     for(auto id : v)
#define fs              first
#define se              second
#define MP              make_pair
#define pb              push_back
#define bit(msk, i)     ((msk >> i) & 1)
#define SZ(v)           (ll)v.size()
#define ALL(v)          v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 5e5 + 7;
const int Mod = 1e9 + 2022;
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 350;

int n, K;
vector<int> ke[N];
int a[N];
int ccnt[N], num_cpn, tot_cpn[N], num_ok;
int nC[N];

int res = INF;

void pdfs (int u, int p) {
    nC[u] = 1;
    iter (&v, ke[u]) {
        if (v != p) {
            pdfs(v, u);
            nC[u] += nC[v];
        }
    }
}

void Assign (int u, int delta) {
    if (delta == 1) {
        if (ccnt[a[u]] == 0) ++num_cpn;
        ccnt[a[u]]++;
        if (ccnt[a[u]] == tot_cpn[a[u]]) ++num_ok;
    }
    else {
        if (ccnt[a[u]] == tot_cpn[a[u]]) --num_ok;
        ccnt[a[u]]--;
        if (ccnt[a[u]] == 0) --num_cpn;
    }
}

void update (int u, int p, int delta) {
    Assign(u, delta);
    iter (&v, ke[u]) {
        if (v != p) update (v, u, delta);
    }
}

void dfs (int u, int p) {
    int mxV = -1;
    iter (&v, ke[u]) if (v != p && (mxV == -1 || nC[v] > nC[mxV])) mxV = v;
    iter (&v, ke[u]) if (v != p && v != mxV) {
        dfs(v, u);
        update (v, u, -1);
    }
    if (mxV != -1) dfs(mxV, u);
    iter (&v, ke[u]) if (v != p && v != mxV) {
        update(v, u, 1);
    }
    Assign (u, 1);
    if (u != 1 && num_ok == num_cpn) {
        res = min(res, min(num_cpn, K - num_cpn));
    }
}

void solution() {
    cin >> n >> K;
    rep (i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        ke[u].pb(v);
        ke[v].pb(u);
    }
    rep (i, 1, n) cin >> a[i], tot_cpn[a[i]]++;
    pdfs(1, 0);
    dfs(1, 0);
    if (res == INF) res = 0;
    cout << res <<"\n";
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug +5
3 4 3
-1 0 0 1 1 2 2
1 0 1 0
3 3
4 4
2 2
*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16328 KB Output is correct
2 Incorrect 32 ms 17108 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12120 KB Output isn't correct
2 Halted 0 ms 0 KB -