Submission #413272

#	Time	Username	Problem	Language	Result	Execution time	Memory
413272		blue	Capital City (JOI20_capital_city)	C++17	100 / 100	1774 ms	98472 KiB

capital_city

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
Draw a directed edge between city A and city B, if there lies a town of city B on the path between two
towns of city A.

Answer = (minimum size of any SCC) - 1


*/
const int maxN = 200000;

int N, K;
vector<int> edge[1+maxN];
int col[1+maxN];
vector<int> col_count(1+maxN, 0);
int parent[1+maxN];



vector<int> order(1);
vector<int> order_index(1+maxN, 0);
vector<int> subtree(1+maxN, 1);


void dfs(int u)
{
    order_index[u] = order.size();
    order.push_back(u);

    for(int v: edge[u])
    {
        if(order_index[v]) continue;
        parent[v] = u;
        dfs(v);
        subtree[u] += subtree[v];
    }
}





struct segtree
{
    int l;
    int r;
    vector<int> v;

    segtree* left = NULL;
    segtree* right = NULL;

    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;

        if(l == r)
        {
            v.push_back(col[ order[l] ]);
        }
        else
        {
            int m = (l+r)/2;
            left = new segtree(l, m);
            right = new segtree(m+1, r);

            for(int x: left->v) v.push_back(x);
            for(int x: right->v) v.push_back(x);
            sort(v.begin(), v.end());
        }
    }

    int count(int L, int R, int V)
    {
        if(R < l || r < L) return 0;
        else if(L <= l && r <= R)
        {
            int i1 = -1, i2 = -1;

            for(int bit = 18; bit >= 0; bit--)
            {
                if(i1 + (1 << bit) >= v.size()) continue;
                if(v[i1 + (1 << bit)] >= V) continue;
                i1 += (1 << bit);
            }
            i1++;

            if(v[i1] != V) return 0;

            for(int bit = 18; bit >= 0; bit--)
            {
                if(i2 + (1 << bit) >= v.size()) continue;
                if(v[i2 + (1 << bit)] > V) continue;
                i2 += (1 << bit);
            }

            return i2-i1+1;
        }
        else
        {
            return left->count(L, R, V) + right->count(L, R, V);
        }
    }
};




vector<int> newEdge[1+maxN];
vector<int> newEdgeRev[1+maxN];

vector<int> scc_dfs_order;
vector<int> visit(1+maxN, 0);

void scc_dfs_1(int u)
{
    for(int v: newEdge[u])
    {
        if(visit[v]) continue;
        visit[v] = 1;
        scc_dfs_1(v);
    }
    scc_dfs_order.push_back(u);
}

int curr_ct;

vector<int> scc_size(1, 0);
vector<int> scc(1+maxN, 0);
int scc_count = 0;

void scc_dfs_2(int u)
{
    scc_size[scc_count]++;
    scc[u] = scc_count;

    for(int v: newEdgeRev[u])
    {
        if(visit[v]) continue;
        visit[v] = 1;
        curr_ct++;
        scc_dfs_2(v);
    }
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> K;

    for(int i = 1; i <= N-1; i++)
    {
        int A, B;
        cin >> A >> B;

        edge[A].push_back(B);
        edge[B].push_back(A);
    }

    for(int i = 1; i <= N; i++)
    {
        cin >> col[i];
        col_count[ col[i] ]++;
    }

    parent[1] = 0;
    dfs(1);

    segtree S(1, N);

    // for(int i = 1; i <= N; i++) cerr << order[i] << ' ';
    // cerr << '\n';
    // for(int i = 1; i <= N; i++) cerr << order_index[i] << ' ';
    // cerr << '\n';

    for(int i = 2; i <= N; i++)
    {
        if(col[i] == col[ parent[i] ]) continue;

        int ct;

        ct = S.count(order_index[i], order_index[i] + subtree[i] - 1, col[parent[i]]);
        if(ct != col_count[ col[parent[i]] ] && ct != 0)
        {
            newEdge[ col[ parent[i] ] ].push_back(col[i]);
            newEdgeRev[ col[i] ].push_back(col[ parent[i] ]);
        }

        ct = S.count(order_index[i], order_index[i] + subtree[i] - 1, col[i]);
        if(ct != col_count[ col[i] ] && ct != 0)
        {
            newEdge[ col[i] ].push_back(col[ parent[i] ]);
            newEdgeRev[ col[parent[i]] ].push_back(col[i]);
        }
    }

    for(int j = 1; j <= K; j++)
    {
        if(visit[j]) continue;
        visit[j] = 1;
        scc_dfs_1(j);
    }

    reverse(scc_dfs_order.begin(), scc_dfs_order.end());

    // for(int j: scc_dfs_order) cerr << j << ' ';
    // cerr << '\n';

    visit = vector<int>(K+1, 0);
    for(int j: scc_dfs_order)
    {
        if(visit[j]) continue;

        scc_count++;
        scc_size.push_back(0);


        visit[j] = 1;
        curr_ct = 1;
        scc_dfs_2(j);

        // cerr << j << ' ' << curr_ct << '\n';
    }

    vector<int> scc_outdegree(scc_count+1, 0);
    for(int u = 1; u <= K; u++)
        for(int v: newEdge[u])
            if(scc[u] != scc[v])
                scc_outdegree[ scc[u] ]++;

    int res = 1e9;
    for(int x = 1; x <= scc_count; x++)
        if(scc_outdegree[x] == 0)
            res = min(res, scc_size[x] - 1);

    // for(int i = 1; i <= K; i++) cerr << scc[i] << ' ' << scc_outdegree[scc[i]] << ' ' << scc_size[scc[i]] << '\n';
    // cerr << '\n';

    cout << res << '\n';
}

Compilation message (stderr)

capital_city.cpp: In member function 'int segtree::count(int, int, int)':
capital_city.cpp:91:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |                 if(i1 + (1 << bit) >= v.size()) continue;
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~
capital_city.cpp:101:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |                 if(i2 + (1 << bit) >= v.size()) continue;
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~

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