oj.uz

답안 #670814

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670814 2022-12-10T17:13:37 Z Kahou 수도 (JOI20_capital_city) C++14
11 / 100
 3000 ms 482656 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 105 ms 193020 KB Output is correct
2 Correct 103 ms 193024 KB Output is correct
3 Correct 106 ms 192992 KB Output is correct
4 Correct 101 ms 193064 KB Output is correct
5 Correct 109 ms 193060 KB Output is correct
6 Correct 101 ms 193048 KB Output is correct
7 Correct 103 ms 193056 KB Output is correct
8 Correct 113 ms 193072 KB Output is correct
9 Correct 105 ms 193036 KB Output is correct
10 Correct 104 ms 193048 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 193020 KB Output is correct
2 Correct 103 ms 193024 KB Output is correct
3 Correct 106 ms 192992 KB Output is correct
4 Correct 101 ms 193064 KB Output is correct
5 Correct 109 ms 193060 KB Output is correct
6 Correct 101 ms 193048 KB Output is correct
7 Correct 103 ms 193056 KB Output is correct
8 Correct 113 ms 193072 KB Output is correct
9 Correct 105 ms 193036 KB Output is correct
10 Correct 104 ms 193048 KB Output is correct
11 Correct 104 ms 193940 KB Output is correct
12 Correct 104 ms 193932 KB Output is correct
13 Correct 107 ms 193836 KB Output is correct
14 Correct 106 ms 193940 KB Output is correct
15 Correct 110 ms 194760 KB Output is correct
16 Correct 107 ms 194548 KB Output is correct
17 Correct 110 ms 194924 KB Output is correct
18 Correct 114 ms 194440 KB Output is correct
19 Correct 105 ms 194688 KB Output is correct
20 Correct 107 ms 194780 KB Output is correct
21 Correct 103 ms 194436 KB Output is correct
22 Correct 114 ms 195092 KB Output is correct
23 Correct 109 ms 194892 KB Output is correct
24 Correct 110 ms 194804 KB Output is correct
25 Correct 108 ms 194892 KB Output is correct
26 Correct 107 ms 194996 KB Output is correct
27 Correct 110 ms 194880 KB Output is correct
28 Correct 109 ms 194836 KB Output is correct
29 Correct 110 ms 194948 KB Output is correct
30 Correct 109 ms 194820 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 193020 KB Output is correct
2 Correct 103 ms 193024 KB Output is correct
3 Correct 106 ms 192992 KB Output is correct
4 Correct 101 ms 193064 KB Output is correct
5 Correct 109 ms 193060 KB Output is correct
6 Correct 101 ms 193048 KB Output is correct
7 Correct 103 ms 193056 KB Output is correct
8 Correct 113 ms 193072 KB Output is correct
9 Correct 105 ms 193036 KB Output is correct
10 Correct 104 ms 193048 KB Output is correct
11 Correct 104 ms 193940 KB Output is correct
12 Correct 104 ms 193932 KB Output is correct
13 Correct 107 ms 193836 KB Output is correct
14 Correct 106 ms 193940 KB Output is correct
15 Correct 110 ms 194760 KB Output is correct
16 Correct 107 ms 194548 KB Output is correct
17 Correct 110 ms 194924 KB Output is correct
18 Correct 114 ms 194440 KB Output is correct
19 Correct 105 ms 194688 KB Output is correct
20 Correct 107 ms 194780 KB Output is correct
21 Correct 103 ms 194436 KB Output is correct
22 Correct 114 ms 195092 KB Output is correct
23 Correct 109 ms 194892 KB Output is correct
24 Correct 110 ms 194804 KB Output is correct
25 Correct 108 ms 194892 KB Output is correct
26 Correct 107 ms 194996 KB Output is correct
27 Correct 110 ms 194880 KB Output is correct
28 Correct 109 ms 194836 KB Output is correct
29 Correct 110 ms 194948 KB Output is correct
30 Correct 109 ms 194820 KB Output is correct
31 Execution timed out 3058 ms 482656 KB Time limit exceeded
32 Halted 0 ms 0 KB -