oj.uz

답안 #1030977

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1030977 2024-07-22T13:11:49 Z dpsaveslives Bosses (BOI16_bosses) C++17
100 / 100
 1036 ms 1148 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5010;
vector<int> adj[MAXN];
vector<int> graph[MAXN],st;
int N,ans,cnt;
void dfs(int u, int p){
    for(auto v : graph[u]){
        if(v != p){
            dfs(v,u);
            st[u] += st[v];
        }
    }
    cnt += st[u];
}
int bfs(int start){
    queue<int> q; q.push(start);
    vector<int> dist(N+1,-1),par(N+1,-1); dist[start] = 0;
    int maxd = -1, ret = 0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(auto v : adj[u]){
            if(dist[v] == -1){
                dist[v] = dist[u]+1;
                par[v] = u;
                q.push(v);
            }
        }
    }
    for(int i = 1;i<=N;++i) graph[i].clear();
    for(int i = 1;i<=N;++i){
        if(dist[i] == -1) return -1;
        graph[par[i]].push_back(i);
    }
    st = vector<int>(N+1,1); cnt = 0;
    dfs(start,0);
    return cnt;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N;
    for(int i = 1;i<=N;++i){
        int k; cin >> k;
        for(int j = 0;j<k;++j){
            int v; cin >> v;
            adj[v].push_back(i);
        }
    }
    int res = -1, root = -1;
    for(int i = 1;i<=N;++i){
        int ret = bfs(i);
        if(ret == -1) continue;
        if(ret < res || res == -1){
            res = ret;
            root = i;
        }
    }
    cout << res << "\n";
    return 0;
}

Compilation message

bosses.cpp: In function 'int bfs(int)':
bosses.cpp:19:9: warning: unused variable 'maxd' [-Wunused-variable]
   19 |     int maxd = -1, ret = 0;
      |         ^~~~
bosses.cpp:19:20: warning: unused variable 'ret' [-Wunused-variable]
   19 |     int maxd = -1, ret = 0;
      |                    ^~~
bosses.cpp: In function 'int main()':
bosses.cpp:50:19: warning: variable 'root' set but not used [-Wunused-but-set-variable]
   50 |     int res = -1, root = -1;
      |                   ^~~~

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 692 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 692 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 692 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 3 ms 828 KB Output is correct
14 Correct 100 ms 1116 KB Output is correct
15 Correct 29 ms 856 KB Output is correct
16 Correct 456 ms 920 KB Output is correct
17 Correct 1036 ms 1112 KB Output is correct
18 Correct 968 ms 1148 KB Output is correct