oj.uz

Submission #413271

# Submission time Handle Problem Language Result Execution time Memory
413271 2021-05-28T12:18:48 Z blue Capital City (JOI20_capital_city) C++17
100 / 100
 2008 ms 102060 KB 
#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()
{
    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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 18252 KB Output is correct
2 Correct 12 ms 18264 KB Output is correct
3 Correct 12 ms 18252 KB Output is correct
4 Correct 12 ms 18276 KB Output is correct
5 Correct 12 ms 18252 KB Output is correct
6 Correct 12 ms 18252 KB Output is correct
7 Correct 12 ms 18248 KB Output is correct
8 Correct 14 ms 18268 KB Output is correct
9 Correct 12 ms 18252 KB Output is correct
10 Correct 12 ms 18252 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 18252 KB Output is correct
2 Correct 12 ms 18264 KB Output is correct
3 Correct 12 ms 18252 KB Output is correct
4 Correct 12 ms 18276 KB Output is correct
5 Correct 12 ms 18252 KB Output is correct
6 Correct 12 ms 18252 KB Output is correct
7 Correct 12 ms 18248 KB Output is correct
8 Correct 14 ms 18268 KB Output is correct
9 Correct 12 ms 18252 KB Output is correct
10 Correct 12 ms 18252 KB Output is correct
11 Correct 17 ms 18820 KB Output is correct
12 Correct 16 ms 18892 KB Output is correct
13 Correct 17 ms 18864 KB Output is correct
14 Correct 17 ms 18920 KB Output is correct
15 Correct 17 ms 18872 KB Output is correct
16 Correct 17 ms 18892 KB Output is correct
17 Correct 16 ms 18856 KB Output is correct
18 Correct 16 ms 18868 KB Output is correct
19 Correct 15 ms 18892 KB Output is correct
20 Correct 16 ms 18872 KB Output is correct
21 Correct 16 ms 18868 KB Output is correct
22 Correct 17 ms 18996 KB Output is correct
23 Correct 18 ms 19020 KB Output is correct
24 Correct 18 ms 18988 KB Output is correct
25 Correct 19 ms 19000 KB Output is correct
26 Correct 19 ms 18964 KB Output is correct
27 Correct 18 ms 18956 KB Output is correct
28 Correct 18 ms 18984 KB Output is correct
29 Correct 19 ms 18976 KB Output is correct
30 Correct 18 ms 18892 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1861 ms 98088 KB Output is correct
2 Correct 645 ms 98380 KB Output is correct
3 Correct 1829 ms 97636 KB Output is correct
4 Correct 644 ms 102060 KB Output is correct
5 Correct 1395 ms 98704 KB Output is correct
6 Correct 647 ms 101900 KB Output is correct
7 Correct 1361 ms 98552 KB Output is correct
8 Correct 595 ms 100732 KB Output is correct
9 Correct 1822 ms 96948 KB Output is correct
10 Correct 1649 ms 94988 KB Output is correct
11 Correct 1594 ms 97276 KB Output is correct
12 Correct 1498 ms 99344 KB Output is correct
13 Correct 1687 ms 94368 KB Output is correct
14 Correct 1506 ms 99592 KB Output is correct
15 Correct 1593 ms 99508 KB Output is correct
16 Correct 1613 ms 95280 KB Output is correct
17 Correct 1586 ms 95816 KB Output is correct
18 Correct 1631 ms 96112 KB Output is correct
19 Correct 1578 ms 98516 KB Output is correct
20 Correct 1529 ms 100204 KB Output is correct
21 Correct 13 ms 18252 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 18252 KB Output is correct
2 Correct 12 ms 18264 KB Output is correct
3 Correct 12 ms 18252 KB Output is correct
4 Correct 12 ms 18276 KB Output is correct
5 Correct 12 ms 18252 KB Output is correct
6 Correct 12 ms 18252 KB Output is correct
7 Correct 12 ms 18248 KB Output is correct
8 Correct 14 ms 18268 KB Output is correct
9 Correct 12 ms 18252 KB Output is correct
10 Correct 12 ms 18252 KB Output is correct
11 Correct 17 ms 18820 KB Output is correct
12 Correct 16 ms 18892 KB Output is correct
13 Correct 17 ms 18864 KB Output is correct
14 Correct 17 ms 18920 KB Output is correct
15 Correct 17 ms 18872 KB Output is correct
16 Correct 17 ms 18892 KB Output is correct
17 Correct 16 ms 18856 KB Output is correct
18 Correct 16 ms 18868 KB Output is correct
19 Correct 15 ms 18892 KB Output is correct
20 Correct 16 ms 18872 KB Output is correct
21 Correct 16 ms 18868 KB Output is correct
22 Correct 17 ms 18996 KB Output is correct
23 Correct 18 ms 19020 KB Output is correct
24 Correct 18 ms 18988 KB Output is correct
25 Correct 19 ms 19000 KB Output is correct
26 Correct 19 ms 18964 KB Output is correct
27 Correct 18 ms 18956 KB Output is correct
28 Correct 18 ms 18984 KB Output is correct
29 Correct 19 ms 18976 KB Output is correct
30 Correct 18 ms 18892 KB Output is correct
31 Correct 1861 ms 98088 KB Output is correct
32 Correct 645 ms 98380 KB Output is correct
33 Correct 1829 ms 97636 KB Output is correct
34 Correct 644 ms 102060 KB Output is correct
35 Correct 1395 ms 98704 KB Output is correct
36 Correct 647 ms 101900 KB Output is correct
37 Correct 1361 ms 98552 KB Output is correct
38 Correct 595 ms 100732 KB Output is correct
39 Correct 1822 ms 96948 KB Output is correct
40 Correct 1649 ms 94988 KB Output is correct
41 Correct 1594 ms 97276 KB Output is correct
42 Correct 1498 ms 99344 KB Output is correct
43 Correct 1687 ms 94368 KB Output is correct
44 Correct 1506 ms 99592 KB Output is correct
45 Correct 1593 ms 99508 KB Output is correct
46 Correct 1613 ms 95280 KB Output is correct
47 Correct 1586 ms 95816 KB Output is correct
48 Correct 1631 ms 96112 KB Output is correct
49 Correct 1578 ms 98516 KB Output is correct
50 Correct 1529 ms 100204 KB Output is correct
51 Correct 13 ms 18252 KB Output is correct
52 Correct 869 ms 86284 KB Output is correct
53 Correct 868 ms 86404 KB Output is correct
54 Correct 864 ms 86528 KB Output is correct
55 Correct 859 ms 86424 KB Output is correct
56 Correct 863 ms 86524 KB Output is correct
57 Correct 861 ms 86272 KB Output is correct
58 Correct 1268 ms 89972 KB Output is correct
59 Correct 1370 ms 90424 KB Output is correct
60 Correct 1201 ms 89364 KB Output is correct
61 Correct 1239 ms 89108 KB Output is correct
62 Correct 646 ms 101984 KB Output is correct
63 Correct 647 ms 101992 KB Output is correct
64 Correct 607 ms 101212 KB Output is correct
65 Correct 647 ms 101920 KB Output is correct
66 Correct 609 ms 91552 KB Output is correct
67 Correct 567 ms 91516 KB Output is correct
68 Correct 592 ms 91604 KB Output is correct
69 Correct 597 ms 91640 KB Output is correct
70 Correct 591 ms 91488 KB Output is correct
71 Correct 572 ms 91448 KB Output is correct
72 Correct 582 ms 91524 KB Output is correct
73 Correct 584 ms 90796 KB Output is correct
74 Correct 608 ms 91632 KB Output is correct
75 Correct 601 ms 91560 KB Output is correct
76 Correct 1511 ms 94004 KB Output is correct
77 Correct 1484 ms 92616 KB Output is correct
78 Correct 1579 ms 95904 KB Output is correct
79 Correct 1601 ms 93980 KB Output is correct
80 Correct 1689 ms 99704 KB Output is correct
81 Correct 1779 ms 97168 KB Output is correct
82 Correct 1728 ms 97216 KB Output is correct
83 Correct 1751 ms 94428 KB Output is correct
84 Correct 2008 ms 99056 KB Output is correct
85 Correct 1540 ms 97816 KB Output is correct
86 Correct 1809 ms 93780 KB Output is correct
87 Correct 1690 ms 95424 KB Output is correct
88 Correct 1802 ms 96144 KB Output is correct
89 Correct 1729 ms 92464 KB Output is correct
90 Correct 1676 ms 92604 KB Output is correct
91 Correct 1750 ms 94712 KB Output is correct
92 Correct 1766 ms 93924 KB Output is correct
93 Correct 1803 ms 93060 KB Output is correct
94 Correct 1851 ms 92496 KB Output is correct
95 Correct 1806 ms 93840 KB Output is correct
96 Correct 1765 ms 93196 KB Output is correct
97 Correct 1797 ms 94732 KB Output is correct