oj.uz

Submission #1085882

# Submission time Handle Problem Language Result Execution time Memory
1085882 2024-09-09T00:51:55 Z underwaterkillerwhale Mergers (JOI19_mergers) C++17
0 / 100
 39 ms 19656 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 ein[N], nC[N];
int dp[N];
int res = 0;

void pdfs (int u, int p) {
    static int time_dfs = 0;
    ein[u] = ++time_dfs;
    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);
    }
    iter (&v, ke[u]) {
        if (v != p) {
            dp[u] += dp[v];
        }
    }

    Assign (u, 1);
    if (u != 1 && num_ok == num_cpn) {
        if (dp[u] == 0) dp[u]++;
//        cout << u <<" "<<p <<"\n";
    }
    if (dp[u] == 0) return;
    if (dp[u] % 2 == 0) {
        res += (dp[u] - 2) / 2;
        dp[u] = 2;
    }
    else {
        res += dp[u] / 2;
        dp[u] = 1;
    }
//    if (num_ok == num_cpn) cout << u <<" "<<dp[u] <<"\n";

//    cout << u <<" "<<p<<" "<<num_cpn<<"\n";
}

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);
    cout << res + ceil(1.0 * dp[1] / 2) <<"\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
9 6
7 6
9 1
2 4
4 5
9 2
8 6
9 3
8 1
3
1
6
4
4
2
5
5
6


*/

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12124 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Correct 6 ms 12124 KB Output is correct
4 Correct 6 ms 12124 KB Output is correct
5 Correct 5 ms 12252 KB Output is correct
6 Correct 6 ms 12124 KB Output is correct
7 Correct 4 ms 12124 KB Output is correct
8 Correct 6 ms 12092 KB Output is correct
9 Correct 5 ms 12124 KB Output is correct
10 Correct 5 ms 12124 KB Output is correct
11 Correct 5 ms 12124 KB Output is correct
12 Correct 5 ms 12124 KB Output is correct
13 Correct 5 ms 12124 KB Output is correct
14 Correct 6 ms 12124 KB Output is correct
15 Correct 5 ms 12124 KB Output is correct
16 Incorrect 5 ms 12124 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12124 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Correct 6 ms 12124 KB Output is correct
4 Correct 6 ms 12124 KB Output is correct
5 Correct 5 ms 12252 KB Output is correct
6 Correct 6 ms 12124 KB Output is correct
7 Correct 4 ms 12124 KB Output is correct
8 Correct 6 ms 12092 KB Output is correct
9 Correct 5 ms 12124 KB Output is correct
10 Correct 5 ms 12124 KB Output is correct
11 Correct 5 ms 12124 KB Output is correct
12 Correct 5 ms 12124 KB Output is correct
13 Correct 5 ms 12124 KB Output is correct
14 Correct 6 ms 12124 KB Output is correct
15 Correct 5 ms 12124 KB Output is correct
16 Incorrect 5 ms 12124 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12124 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Correct 6 ms 12124 KB Output is correct
4 Correct 6 ms 12124 KB Output is correct
5 Correct 5 ms 12252 KB Output is correct
6 Correct 6 ms 12124 KB Output is correct
7 Correct 4 ms 12124 KB Output is correct
8 Correct 6 ms 12092 KB Output is correct
9 Correct 5 ms 12124 KB Output is correct
10 Correct 5 ms 12124 KB Output is correct
11 Correct 5 ms 12124 KB Output is correct
12 Correct 5 ms 12124 KB Output is correct
13 Correct 5 ms 12124 KB Output is correct
14 Correct 6 ms 12124 KB Output is correct
15 Correct 5 ms 12124 KB Output is correct
16 Incorrect 5 ms 12124 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 18384 KB Output is correct
2 Incorrect 39 ms 19656 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12124 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Correct 6 ms 12124 KB Output is correct
4 Correct 6 ms 12124 KB Output is correct
5 Correct 5 ms 12252 KB Output is correct
6 Correct 6 ms 12124 KB Output is correct
7 Correct 4 ms 12124 KB Output is correct
8 Correct 6 ms 12092 KB Output is correct
9 Correct 5 ms 12124 KB Output is correct
10 Correct 5 ms 12124 KB Output is correct
11 Correct 5 ms 12124 KB Output is correct
12 Correct 5 ms 12124 KB Output is correct
13 Correct 5 ms 12124 KB Output is correct
14 Correct 6 ms 12124 KB Output is correct
15 Correct 5 ms 12124 KB Output is correct
16 Incorrect 5 ms 12124 KB Output isn't correct
17 Halted 0 ms 0 KB -