제출 #164137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
164137		combi1k1	Mergers (JOI19_mergers)	C++14	70 / 100	1760 ms	149012 KiB

mergers

#include<bits/stdc++.h>

using namespace std;

const int   N   = 5e5 + 1;

vector<int> g[N];
vector<int> a[N];
vector<int> s[N];

int st[N], en[N];
int tot = 0;

int f[N];
int h[N];
int p[N][20];

int dfs(int u)  {
    st[u] = ++tot;
    for(int i = 0 ; i < 16 ; ++i)
        p[u][i + 1] = p[p[u][i]][i];
    for(int v : g[u])   if (v != p[u][0])   {
        h[v] = h[u] + 1;
        p[v][0] = u;
        dfs(v);
    }
    en[u] = tot;

    return  1;
}
int par(int u,int d)    {
    for(int i = 0 ; i < 17 ; ++i)   if (d >> i & 1)
        u = p[u][i];
    return  u;
}
int lca(int u,int v)    {
    if (h[u] < h[v])
        swap(u,v);
    u = par(u,h[u] - h[v]);

    if (u == v) return  u;

    for(int i = 16 ; i >= 0 ; --i)  if (p[u][i] != p[v][i]) {
        u = p[u][i];
        v = p[v][i];
    }

    return  p[u][0];
}
int upd(int u)  {
    for(int v : g[u])   if (v != p[u][0])
        upd(v), f[u] += f[v];
    return  1;
}
int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int k;  cin >> k;

    for(int i = 2 ; i <= n ; ++i)   {
        int x;  cin >> x;
        int y;  cin >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i = 1 ; i <= n ; ++i)   {
        int x;  cin >> x;
        s[x].push_back(i);
    }

    dfs(1);

    auto cmp = [&](int x,int y) {
        return  st[x] < st[y];
    };
    auto con = [&](vector<int> v,int x,int y)   {
        sort(v.begin(),v.end(),cmp);    v.erase(unique(v.begin(),v.end()),v.end());

        for(int j = 1, K = v.size() ; j < K ; ++j)
            v.push_back(lca(v[j - 1],v[j]));

        sort(v.begin(),v.end(),cmp);    v.erase(unique(v.begin(),v.end()),v.end());

        stack<int>  T;

        for(int a : v)  {
            for(; T.size() && en[T.top()] < en[a] ; T.pop());
            if (T.size())
                f[T.top()] += x,
                f[a] += y;
            T.push(a);
        }
    };

    for(int i = 1 ; i <= k ; ++i)   con(s[i],-1,1);

    upd(1);

    vector<int> vec;

    for(int i = 2 ; i <= n ; ++i)   if(!f[i])
        vec.push_back(i),
        vec.push_back(p[i][0]);

    memset(f,0,sizeof f);

    con(vec,1,1);

    int cnt = 0;

    for(int i = 1 ; i <= n ; ++i)   if (f[i] == 1)
        cnt++;

    cout << (cnt + 1) / 2 << endl;
}

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