oj.uz

Submission #938194

# Submission time Handle Problem Language Result Execution time Memory
938194 2024-03-05T02:10:29 Z Pring Capital City (JOI20_capital_city) C++17
100 / 100
 2947 ms 480840 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
#define debug(x...) cout << '[' << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

// #define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 200005;
int n, k;
vector<int> clr[MXN];

namespace GRAPH {
    int nc;
    vector<int> edge[MXN * 20];
    int dfn[MXN * 20], low[MXN * 20], scc[MXN * 20], ns, C;
    vector<int> st;
    int out[MXN * 20];

    void ADD_EDGE(int x, int y) {
        edge[x].push_back(y);
    }

    void DFS(int id) {
        C++;
        dfn[id] = C;
        low[id] = C;
        st.push_back(id);
        for (auto &i : edge[id]) {
            if (scc[i]) continue;
            if (dfn[i]) {
                low[id] = min(low[id], dfn[i]);
            } else {
                DFS(i);
                low[id] = min(low[id], low[i]);
            }
        }
        if (dfn[id] == low[id]) {
            int x;
            ns++;
            do {
                x = st.back();
                st.pop_back();
                scc[x] = ns;
            } while (x != id);
        }
    }

    void SCC() {
        FOR(i, 1, nc + 1) {
            if (dfn[i]) continue;
            DFS(i);
        }
    }

    int GET_ANS() {
        FOR(id, 1, nc + 1) {
            for (auto &i : edge[id]) {
                if (scc[i] == scc[id]) continue;
                out[scc[id]]++;
            }
        }
        map<int, int> M;
        FOR(i, n + 1, n + k + 1) if (out[scc[i]] == 0) M[scc[i]]++;
        int ans = INT_MAX;
        for (auto i : M) ans = min(ans, i.sc);
        return ans;
    }
}

namespace TREE {
    vector<int> edge[MXN], lf[MXN];
    vector<int> p[MXN];
    int d[MXN];
    
    void ADD_EDGE(int x, int y) {
        edge[x].push_back(y);
        edge[y].push_back(x);
    }

    void DFS(int id, int par, int dep) {
        p[id].push_back(par);
        d[id] = dep;
        for (auto &i : edge[id]) {
            if (i == par) continue;
            DFS(i, id, dep + 1);
        }
    }

    void LIFT() {
        DFS(1, 1, 0);
        FOR(i, 1, n + 1) lf[i].push_back(i);
        for(int w = 1; (1 << w) <= n; w++) {
            debug(w);
            FOR(i, 1, n + 1) {
                int now = ++GRAPH::nc;
                GRAPH::ADD_EDGE(now, lf[i][w - 1]);
                GRAPH::ADD_EDGE(now, lf[p[i].back()][w - 1]);
                lf[i].push_back(now);
            }
            FOR(i, 1, n + 1) {
                // debug(i, p[p[i][w - 1]][w - 1]);
                p[i].push_back(p[p[i][w - 1]][w - 1]);
            }
        }
    }

    int leap(int x, int k, int c) {
        for (int w = p[1].size() - 1; w >= 0; w--) if (k & (1 << w)) {
            if (c != -1) GRAPH::ADD_EDGE(c, lf[x][w]);
            x = p[x][w];
        }
        return x;
    }

    int lca(int x, int y) {
        if (d[x] < d[y]) swap(x, y);
        x = leap(x, d[x] - d[y], -1);
        if (x == y) return x;
        for (int w = p[1].size() - 1; w >= 0; w--) {
            if (p[x][w] == p[y][w]) continue;
            x = p[x][w];
            y = p[y][w];
        }
        return p[x][0];
    }

    void BUILD(vector<int> v, int c) {
        int lca_now = v.back();
        for (auto &i : v) lca_now = lca(lca_now, i);
        for (auto &i : v) leap(i, d[i] - d[lca_now], c);
        GRAPH::ADD_EDGE(c, lca_now);
    }
}

void miku() {
    int a, b;
    cin >> n >> k;
    GRAPH::nc = n + k;
    FOR(i, 1, n) {
        cin >> a >> b;
        TREE::ADD_EDGE(a, b);
    }
    FOR(i, 1, n + 1) {
        cin >> a;
        clr[a].push_back(i);
        GRAPH::ADD_EDGE(i, a + n);
    }
    TREE::LIFT();
    FOR(i, 1, k + 1) {
        TREE::BUILD(clr[i], i + n);
    }
    GRAPH::SCC();
    cout << GRAPH::GET_ANS() - 1 << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(iostream::failbit);
    miku();
    return 0;
}

Compilation message

capital_city.cpp: In function 'void TREE::LIFT()':
capital_city.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
capital_city.cpp:105:13: note: in expansion of macro 'debug'
  105 |             debug(w);
      |             ^~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 120928 KB Output is correct
2 Correct 27 ms 120864 KB Output is correct
3 Correct 27 ms 120808 KB Output is correct
4 Correct 29 ms 120864 KB Output is correct
5 Correct 27 ms 121176 KB Output is correct
6 Correct 28 ms 120924 KB Output is correct
7 Correct 28 ms 120916 KB Output is correct
8 Correct 27 ms 120872 KB Output is correct
9 Correct 27 ms 120924 KB Output is correct
10 Correct 27 ms 120996 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 120928 KB Output is correct
2 Correct 27 ms 120864 KB Output is correct
3 Correct 27 ms 120808 KB Output is correct
4 Correct 29 ms 120864 KB Output is correct
5 Correct 27 ms 121176 KB Output is correct
6 Correct 28 ms 120924 KB Output is correct
7 Correct 28 ms 120916 KB Output is correct
8 Correct 27 ms 120872 KB Output is correct
9 Correct 27 ms 120924 KB Output is correct
10 Correct 27 ms 120996 KB Output is correct
11 Correct 32 ms 122200 KB Output is correct
12 Correct 31 ms 122196 KB Output is correct
13 Correct 31 ms 122204 KB Output is correct
14 Correct 32 ms 122240 KB Output is correct
15 Correct 30 ms 122104 KB Output is correct
16 Correct 31 ms 122200 KB Output is correct
17 Correct 31 ms 122200 KB Output is correct
18 Correct 31 ms 122204 KB Output is correct
19 Correct 31 ms 122448 KB Output is correct
20 Correct 32 ms 122204 KB Output is correct
21 Correct 32 ms 122348 KB Output is correct
22 Correct 31 ms 122964 KB Output is correct
23 Correct 31 ms 122540 KB Output is correct
24 Correct 30 ms 122192 KB Output is correct
25 Correct 31 ms 122204 KB Output is correct
26 Correct 31 ms 122464 KB Output is correct
27 Correct 31 ms 122412 KB Output is correct
28 Correct 31 ms 122228 KB Output is correct
29 Correct 32 ms 122204 KB Output is correct
30 Correct 31 ms 122336 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2882 ms 473744 KB Output is correct
2 Correct 877 ms 480240 KB Output is correct
3 Correct 2947 ms 468876 KB Output is correct
4 Correct 909 ms 480688 KB Output is correct
5 Correct 2813 ms 430792 KB Output is correct
6 Correct 857 ms 478228 KB Output is correct
7 Correct 2717 ms 449836 KB Output is correct
8 Correct 807 ms 458880 KB Output is correct
9 Correct 2159 ms 370992 KB Output is correct
10 Correct 2164 ms 368500 KB Output is correct
11 Correct 2185 ms 370664 KB Output is correct
12 Correct 2221 ms 374056 KB Output is correct
13 Correct 2186 ms 369668 KB Output is correct
14 Correct 2231 ms 374012 KB Output is correct
15 Correct 2284 ms 372468 KB Output is correct
16 Correct 2191 ms 369484 KB Output is correct
17 Correct 2231 ms 371464 KB Output is correct
18 Correct 2225 ms 369748 KB Output is correct
19 Correct 2255 ms 371896 KB Output is correct
20 Correct 2275 ms 374184 KB Output is correct
21 Correct 28 ms 120924 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 120928 KB Output is correct
2 Correct 27 ms 120864 KB Output is correct
3 Correct 27 ms 120808 KB Output is correct
4 Correct 29 ms 120864 KB Output is correct
5 Correct 27 ms 121176 KB Output is correct
6 Correct 28 ms 120924 KB Output is correct
7 Correct 28 ms 120916 KB Output is correct
8 Correct 27 ms 120872 KB Output is correct
9 Correct 27 ms 120924 KB Output is correct
10 Correct 27 ms 120996 KB Output is correct
11 Correct 32 ms 122200 KB Output is correct
12 Correct 31 ms 122196 KB Output is correct
13 Correct 31 ms 122204 KB Output is correct
14 Correct 32 ms 122240 KB Output is correct
15 Correct 30 ms 122104 KB Output is correct
16 Correct 31 ms 122200 KB Output is correct
17 Correct 31 ms 122200 KB Output is correct
18 Correct 31 ms 122204 KB Output is correct
19 Correct 31 ms 122448 KB Output is correct
20 Correct 32 ms 122204 KB Output is correct
21 Correct 32 ms 122348 KB Output is correct
22 Correct 31 ms 122964 KB Output is correct
23 Correct 31 ms 122540 KB Output is correct
24 Correct 30 ms 122192 KB Output is correct
25 Correct 31 ms 122204 KB Output is correct
26 Correct 31 ms 122464 KB Output is correct
27 Correct 31 ms 122412 KB Output is correct
28 Correct 31 ms 122228 KB Output is correct
29 Correct 32 ms 122204 KB Output is correct
30 Correct 31 ms 122336 KB Output is correct
31 Correct 2882 ms 473744 KB Output is correct
32 Correct 877 ms 480240 KB Output is correct
33 Correct 2947 ms 468876 KB Output is correct
34 Correct 909 ms 480688 KB Output is correct
35 Correct 2813 ms 430792 KB Output is correct
36 Correct 857 ms 478228 KB Output is correct
37 Correct 2717 ms 449836 KB Output is correct
38 Correct 807 ms 458880 KB Output is correct
39 Correct 2159 ms 370992 KB Output is correct
40 Correct 2164 ms 368500 KB Output is correct
41 Correct 2185 ms 370664 KB Output is correct
42 Correct 2221 ms 374056 KB Output is correct
43 Correct 2186 ms 369668 KB Output is correct
44 Correct 2231 ms 374012 KB Output is correct
45 Correct 2284 ms 372468 KB Output is correct
46 Correct 2191 ms 369484 KB Output is correct
47 Correct 2231 ms 371464 KB Output is correct
48 Correct 2225 ms 369748 KB Output is correct
49 Correct 2255 ms 371896 KB Output is correct
50 Correct 2275 ms 374184 KB Output is correct
51 Correct 28 ms 120924 KB Output is correct
52 Correct 1096 ms 370832 KB Output is correct
53 Correct 1087 ms 370472 KB Output is correct
54 Correct 1087 ms 370464 KB Output is correct
55 Correct 1092 ms 371128 KB Output is correct
56 Correct 1072 ms 370788 KB Output is correct
57 Correct 1050 ms 370520 KB Output is correct
58 Correct 1917 ms 375612 KB Output is correct
59 Correct 1850 ms 376632 KB Output is correct
60 Correct 1900 ms 368200 KB Output is correct
61 Correct 1920 ms 368440 KB Output is correct
62 Correct 874 ms 480840 KB Output is correct
63 Correct 844 ms 480072 KB Output is correct
64 Correct 832 ms 462940 KB Output is correct
65 Correct 881 ms 477872 KB Output is correct
66 Correct 1774 ms 373256 KB Output is correct
67 Correct 1847 ms 372532 KB Output is correct
68 Correct 1835 ms 374128 KB Output is correct
69 Correct 1737 ms 372812 KB Output is correct
70 Correct 1679 ms 373476 KB Output is correct
71 Correct 1758 ms 372936 KB Output is correct
72 Correct 1642 ms 373340 KB Output is correct
73 Correct 1712 ms 372376 KB Output is correct
74 Correct 1719 ms 373972 KB Output is correct
75 Correct 1672 ms 374108 KB Output is correct
76 Correct 1382 ms 374184 KB Output is correct
77 Correct 1435 ms 369896 KB Output is correct
78 Correct 2264 ms 370160 KB Output is correct
79 Correct 2327 ms 368520 KB Output is correct
80 Correct 2275 ms 374816 KB Output is correct
81 Correct 2281 ms 371396 KB Output is correct
82 Correct 2285 ms 371496 KB Output is correct
83 Correct 2243 ms 369032 KB Output is correct
84 Correct 2341 ms 373964 KB Output is correct
85 Correct 2317 ms 371124 KB Output is correct
86 Correct 2253 ms 367636 KB Output is correct
87 Correct 2370 ms 370396 KB Output is correct
88 Correct 2189 ms 371676 KB Output is correct
89 Correct 2130 ms 368380 KB Output is correct
90 Correct 2174 ms 368240 KB Output is correct
91 Correct 2185 ms 368696 KB Output is correct
92 Correct 2152 ms 369988 KB Output is correct
93 Correct 2232 ms 369812 KB Output is correct
94 Correct 2073 ms 368052 KB Output is correct
95 Correct 2118 ms 370288 KB Output is correct
96 Correct 2146 ms 367968 KB Output is correct
97 Correct 2176 ms 369676 KB Output is correct