Submission #886322

#	Time	Username	Problem	Language	Result	Execution time	Memory
886322		maxFedorchuk	Mergers (JOI19_mergers)	C++14	100 / 100	535 ms	80928 KiB

mergers

#include <bits/stdc++.h>
using namespace std;
int c[500005], l[500005], r[500005], t, t2, ans;
vector<int> adj[500005];
void f(int u, int p)
{
    t++;
    if (!l[c[u]])
        l[c[u]]=t;
    for (int v:adj[u])
        if (v!=p)
            f(v, u);
    r[c[u]]=t;
}
pair<pair<int, int>, int> f2(int u, int p)
{
    t2++;
    int t3=t2, x=l[c[u]], y=r[c[u]], z=0;
    for (int v:adj[u])
    {
        if (v!=p)
        {
            pair<pair<int, int>, int> r=f2(v, u);
            x=min(x, r.first.first);
            y=max(y, r.first.second);
            z+=r.second;
        }
    }
    if (!p)
        ans+=(z==1);
    else if (x==t3 && y==t2)
    {
        ans+=!z;
        z=1;
    }
    return {{x, y}, z};
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i=1; i<n; 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 >> c[i];
    f(1, 0);
    f2(1, 0);
    cout << (ans+1)/2;
    return 0;
}

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