Submission #1264664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264664		tvgk	Capital City (JOI20_capital_city)	C++20	100 / 100	363 ms	88632 KiB

capital_city

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e5 + 7;

int h[mxN], par[mxN], in[mxN], n, k, arr[mxN], out[mxN], tree[mxN * 4], c[mxN], num, stt, root[mxN], ans, mn[mxN];
vector<int> w[mxN], path[mxN * 5];

void DFS(int j)
{
    int mem = h[j] = h[par[j]] + 1;

    for (int i : w[j])
    {
        if (h[i])
            continue;

        par[i] = j;
        DFS(i);
        mem = max(mem, h[i]);
    }
    h[j] = mem;
}

bool cmp(int u, int v)
{
    return h[u] > h[v];
}

void TiTo(int j)
{
    in[j] = ++num;
    arr[num] = c[j];

    sort(w[j].begin(), w[j].end(), cmp);

    if (!stt)
        stt = j;
    root[j] = stt;

    for (int i : w[j])
    {
        if (in[i])
            continue;

        TiTo(i);
    }
    stt = 0;
    out[j] = num;
}

void Upd(int u, int v, int id, int j = 1, int l = 1, int r = n)
{
    if (l > v || u > r)
        return;

    if (u <= l && r <= v)
    {
        path[id].push_back(j + k);
        return;
    }

    int mid = (l + r) / 2;
    Upd(u, v, id, j * 2, l, mid);
    Upd(u, v, id, j * 2 + 1, mid + 1, r);
}

int LCA(int u, int v)
{
    int tmp = c[v];
    while (u != v)
    {
        if (in[u] > in[v])
            swap(u, v);

        if (root[u] == root[v])
        {
            Upd(in[u], in[v], tmp);
            return u;
        }
        Upd(in[root[v]], in[v], tmp);
        v = par[root[v]];
    }
}

void Build(int j = 1, int l = 1, int r = n)
{
    if (l == r)
    {
        path[j + k].push_back(arr[l]);
        return;
    }

    int mid = (l + r) / 2;
    path[j + k].push_back(j * 2 + k);
    path[j + k].push_back(j * 2 + 1 + k);
    Build(j * 2, l, mid);
    Build(j * 2 + 1, mid + 1, r);
}

int low[mxN * 5], vis[mxN * 5];
bool tt[mxN * 5];
vector<int> vc;
void Tarzan(int j)
{
    int tmp = low[j] = ++num;
    vis[j] = 1;
    tt[j] = 1;
    vc.push_back(j);

    for (int i : path[j])
    {
        if (!vis[i])
            Tarzan(i);

        if (vis[i] == 1)
            low[j] = min(low[i], low[j]);
        tt[j] &= tt[i];
    }

    if (low[j] != tmp)
        return;

    bool lf = tt[j];
    int cntt = 0;
    while (vis[j] == 1)
    {
        vis[vc.back()] = 2;
        tt[vc.back()] = 0;
        cntt += (vc.back() <= k);

        vc.pop_back();
    }

    if (lf)
        ans = min(ans, cntt - 1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> k;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        w[u].push_back(v);
        w[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        cin >> c[i];

    DFS(1);
    TiTo(1);
    Build(1);

    for (int i = 1; i <= n; i++)
    {
        if (mn[c[i]])
            mn[c[i]] = LCA(mn[c[i]], i);
        else
            mn[c[i]] = i;
    }

//    for (int i = 1; i <= n * 3; i++)
//    {
//        cout << i << " : ";
//        for (int j : path[i])
//            cout << j << " ";
//        cout << '\n';
//    }

    ans = n;
    for (int i = 1; i <= k; i++)
    {
        if (!vis[i])
            Tarzan(i);
    }
    cout << ans;
}

Compilation message (stderr)

capital_city.cpp: In function 'int LCA(int, int)':
capital_city.cpp:88:1: warning: control reaches end of non-void function [-Wreturn-type]
   88 | }
      | ^

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 59 / 59