Submission #261881

#	Time	Username	Problem	Language	Result	Execution time	Memory
261881		Kastanda	Capital City (JOI20_capital_city)	C++11	100 / 100	475 ms	66036 KiB

capital_city

// M
#include<bits/stdc++.h>
using namespace std;
const int N = 200005, LG = 18;
int n, k, cp, A[N], H[N], P[N][LG], M[N], C[N], SZ[N], lca[N];
vector < int > TP, Adj[N], Out[N], In[N], V[N];
void DFS(int v, int p)
{
        P[v][0] = p;
        for (int j = 1; j < LG; j ++)
                P[v][j] = P[P[v][j - 1]][j - 1];
        for (int u : Adj[v])
                if (u != p)
                        H[u] = H[v] + 1, DFS(u, v);
}
inline int LCA(int v, int u)
{
        if (H[v] < H[u])
                swap(v, u);
        for (int i = 0; i < LG; i ++)
                if ((H[v] - H[u]) >> i & 1)
                        v = P[v][i];
        if (v == u)
                return v;
        for (int i = LG - 1; ~ i; i --)
                if (P[v][i] != P[u][i])
                        v = P[v][i], u = P[u][i];
        return P[v][0];
}
void DFS2(int v)
{
        M[v] = 1;
        for (int u : Out[v])
                if (!M[u]) DFS2(u);
        TP.push_back(v);
}
void DFS3(int v)
{
        C[v] = cp;
        for (int u : In[v])
                if (!C[u]) DFS3(u);
}
int main()
{
        scanf("%d%d", &n, &k);
        for (int i = 1; i < n; i ++)
        {
                int v, u;
                scanf("%d%d", &v, &u);
                Adj[v].push_back(u);
                Adj[u].push_back(v);
        }
        for (int i = 1; i <= n; i ++)
                scanf("%d", &A[i]), V[A[i]].push_back(i);
        DFS(1, 0);
        for (int i = 1; i <= k; i ++)
        {
                lca[i] = V[i][0];
                for (int v : V[i])
                        lca[i] = LCA(lca[i], v);
        }
        for (int i = 2; i <= n; i ++)
                if (A[i] != A[P[i][0]] && i != lca[A[i]])
                        Out[A[i]].push_back(A[P[i][0]]),
                        In[A[P[i][0]]].push_back(A[i]);
        for (int i = 1; i <= k; i ++)
                if (!M[i]) DFS2(i);
        reverse(TP.begin(), TP.end());
        for (int v : TP)
                if (!C[v]) ++ cp, DFS3(v);
        memset(M, 0, sizeof(M));
        for (int i = 1; i <= k; i ++)
        {
                SZ[C[i]] ++;
                for (int v : Out[i])
                        if (C[v] != C[i])
                                M[C[i]] = 1;
        }
        int Mn = k;
        for (int i = 1; i <= cp; i ++)
                if (!M[i]) Mn = min(Mn, SZ[i]);
        return !printf("%d\n", Mn - 1);
}

Compilation message (stderr)

capital_city.cpp: In function 'int main()':
capital_city.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &n, &k);
         ~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:49:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d", &v, &u);
                 ~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:54:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d", &A[i]), V[A[i]].push_back(i);
                 ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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