oj.uz

답안 #670802

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670802 2022-12-10T14:51:22 Z Kahou 수도 (JOI20_capital_city) C++14
11 / 100
 3000 ms 482876 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
/* In the name of God, aka Allah */
// let this be mytemp.cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 2e5 + 50, LG = 18, M = 4e6 + 50;
int n, k, c[N], h[N], m, id[LG][N], par[LG][N];
bool mark[M];
bool vis[M];
int scc[M], cnt[M];
int r[N];
vector<int> topol;
vector<int> adj[N], adj2[2][M];

int t;

void dfs(int u, int p) {
        h[u] = h[p]+1;
        par[0][u] = p;
        for (int v:adj[u]) {
                if (v == p) continue;
                dfs(v, u);
        }
}
int LCA(int u, int v) {
        if (h[u] > h[v]) swap(u, v);
        for (int x = LG-1; x >= 0; x--) {
                if ((h[v]-h[u])>>x&1) v = par[x][v];
        }
        for (int x = LG-1; x >= 0; x--) {
                if (par[x][u] != par[x][v]) u = par[x][u], v= par[x][v];
        }
        if (u == v) return u;
        return par[0][u];
}
void add_edge(int u, int v) {
        int x = c[u];
        for (int t = LG-1; t >= 0; t--) {
                if ((h[u]-h[v]+1)>>t&1) {
                        adj2[0][x].push_back(id[t][u]);
                        adj2[1][id[t][u]].push_back(x);
                        u = par[t][u];
                }
        }
}
void dfs2(int u) {
        vis[u] = 1;
        for (int v:adj2[1][u]){
                if (vis[v]) continue;
                dfs2(v);
        }
        topol.push_back(u);
}
void sfd(int u) {
        scc[u] = t;
        for (int v:adj2[0][u]) {
                if (scc[v]) {
                        mark[t] = mark[t] || (scc[v] != t);
                        continue;
                }
                sfd(v);
        }
}

void solve() {
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n-1; i++) {
                int u, v;
                scanf("%d%d", &u, &v);
                adj[u].push_back(v), adj[v].push_back(u);
        }
        for (int u = 1; u <= n; u++) {
                scanf("%d", &c[u]);
                r[c[u]] = u;
        }
        m = k;
        dfs(1, 0);
        for (int x = 1; x < LG; x++) {
                for (int u = 1; u <= n; u++) {
                        par[x][u] = par[x-1][par[x-1][u]];
                }
        }

        for (int x = 0; x < LG; x++) {
                for (int u = 1; u <= n; u++) {
                        if (h[u] < (1<<x)) continue;
                        id[x][u] = ++m;
                        if (!x) {
                                adj2[0][id[x][u]].push_back(c[u]);
                                adj2[1][c[u]].push_back(id[x][u]);
                        }
                        else {
                                adj2[0][id[x][u]].push_back(id[x-1][u]);
                                adj2[0][id[x][u]].push_back(id[x-1][par[x-1][u]]);
                                adj2[1][id[x-1][u]].push_back(id[x][u]);
                                adj2[1][id[x-1][par[x-1][u]]].push_back(id[x][u]);
                        }
                }
        }
        for (int u = 1; u <= n; u++) {
                r[c[u]] = LCA(r[c[u]], u);
        }
        for (int u = 1; u <= n; u++) {
                add_edge(u, r[c[u]]);
        }
        for (int u = 1; u <= k; u++) {
                if (!vis[u]) dfs2(u);
        }

        for (int i = (int)topol.size() - 1; i >= 0; i--) {
                int u = topol[i];
                if (scc[u]) continue;
                t++;
                sfd(u);
        }
        for (int x = 1; x <= k; x++) {
                cnt[scc[x]]++;
        }

        int ans = N;
        for (int x = 1; x <= t; x++) {
                if (mark[x]) continue;
                ans = min(ans, cnt[x]);
        }
        printf("%d", ans-1);
}

int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        solve();
        return 0;
}

Compilation message

capital_city.cpp: In function 'void solve()':
capital_city.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%d%d", &n, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:79:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |                 scanf("%d%d", &u, &v);
      |                 ~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:83:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |                 scanf("%d", &c[u]);
      |                 ~~~~~^~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 192972 KB Output is correct
2 Correct 101 ms 193040 KB Output is correct
3 Correct 98 ms 193048 KB Output is correct
4 Correct 105 ms 192972 KB Output is correct
5 Correct 106 ms 192960 KB Output is correct
6 Correct 99 ms 192992 KB Output is correct
7 Correct 100 ms 192972 KB Output is correct
8 Correct 104 ms 193028 KB Output is correct
9 Correct 100 ms 193152 KB Output is correct
10 Correct 100 ms 192940 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 192972 KB Output is correct
2 Correct 101 ms 193040 KB Output is correct
3 Correct 98 ms 193048 KB Output is correct
4 Correct 105 ms 192972 KB Output is correct
5 Correct 106 ms 192960 KB Output is correct
6 Correct 99 ms 192992 KB Output is correct
7 Correct 100 ms 192972 KB Output is correct
8 Correct 104 ms 193028 KB Output is correct
9 Correct 100 ms 193152 KB Output is correct
10 Correct 100 ms 192940 KB Output is correct
11 Correct 105 ms 193872 KB Output is correct
12 Correct 111 ms 194004 KB Output is correct
13 Correct 109 ms 193864 KB Output is correct
14 Correct 106 ms 193896 KB Output is correct
15 Correct 105 ms 194696 KB Output is correct
16 Correct 112 ms 194508 KB Output is correct
17 Correct 108 ms 194888 KB Output is correct
18 Correct 104 ms 194428 KB Output is correct
19 Correct 116 ms 194612 KB Output is correct
20 Correct 106 ms 194888 KB Output is correct
21 Correct 119 ms 194512 KB Output is correct
22 Correct 119 ms 195016 KB Output is correct
23 Correct 119 ms 194892 KB Output is correct
24 Correct 111 ms 194696 KB Output is correct
25 Correct 111 ms 194892 KB Output is correct
26 Correct 106 ms 194952 KB Output is correct
27 Correct 106 ms 194844 KB Output is correct
28 Correct 110 ms 194832 KB Output is correct
29 Correct 106 ms 194848 KB Output is correct
30 Correct 109 ms 194840 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3093 ms 482876 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 192972 KB Output is correct
2 Correct 101 ms 193040 KB Output is correct
3 Correct 98 ms 193048 KB Output is correct
4 Correct 105 ms 192972 KB Output is correct
5 Correct 106 ms 192960 KB Output is correct
6 Correct 99 ms 192992 KB Output is correct
7 Correct 100 ms 192972 KB Output is correct
8 Correct 104 ms 193028 KB Output is correct
9 Correct 100 ms 193152 KB Output is correct
10 Correct 100 ms 192940 KB Output is correct
11 Correct 105 ms 193872 KB Output is correct
12 Correct 111 ms 194004 KB Output is correct
13 Correct 109 ms 193864 KB Output is correct
14 Correct 106 ms 193896 KB Output is correct
15 Correct 105 ms 194696 KB Output is correct
16 Correct 112 ms 194508 KB Output is correct
17 Correct 108 ms 194888 KB Output is correct
18 Correct 104 ms 194428 KB Output is correct
19 Correct 116 ms 194612 KB Output is correct
20 Correct 106 ms 194888 KB Output is correct
21 Correct 119 ms 194512 KB Output is correct
22 Correct 119 ms 195016 KB Output is correct
23 Correct 119 ms 194892 KB Output is correct
24 Correct 111 ms 194696 KB Output is correct
25 Correct 111 ms 194892 KB Output is correct
26 Correct 106 ms 194952 KB Output is correct
27 Correct 106 ms 194844 KB Output is correct
28 Correct 110 ms 194832 KB Output is correct
29 Correct 106 ms 194848 KB Output is correct
30 Correct 109 ms 194840 KB Output is correct
31 Execution timed out 3093 ms 482876 KB Time limit exceeded
32 Halted 0 ms 0 KB -