제출 #243664

#제출 시각아이디문제언어결과실행 시간메모리
243664kimbj0709Bosses (BOI16_bosses)C++14
0 / 100
5 ms736 KiB
#include <bits/stdc++.h> using namespace std; #define maxn 5050 #define int long long vector<vector<int> > adj(maxn); int32_t main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int no_of_input,no_of_input1,input; cin >> no_of_input; for(int i=1;i<=no_of_input;i++){ cin >> no_of_input1; for(int j=0;j<no_of_input1;j++){ cin >> input; //adj[i].push_back(input); adj[input].push_back(i); } } int ans = INT_MAX; for(int i=1;i<=no_of_input;i++){//tree rooted at node i deque<pair<int,int> > q1; deque<int> q2; vector<int> dist(maxn,INT_MAX); vector<int> parent(maxn,0); q1.push_back({i,0}); dist[i] = 0; while(q1.size()!=0){ pair<int,int> a = q1.front(); q1.pop_front(); for(auto k:adj[a.first]){ if(a.second+1<dist[k]){ dist[k] = a.second+1; parent[k] = a.first; q1.push_back({k,dist[k]}); } } } vector<int> haschild(maxn,0); for(int j=1;j<=no_of_input;j++){ if(j==i){ continue; } haschild[parent[j]]++; } vector<int> visited(maxn,0); for(int j=1;j<=no_of_input;j++){ if(haschild[j]==0){ q2.push_back(j); visited[j] = 1; } } for(int j=1;j<=no_of_input;j++){ dist[j] = 1; } while(q2.size()!=0){ int a = q2.front(); q2.pop_front(); if(parent[a]==-1){ continue; } dist[parent[a]] += dist[a]; if(visited[parent[a]]==1){ continue; } visited[parent[a]] = 1; q2.push_back(parent[a]); } int sum = 0; for(int j=1;j<=no_of_input;j++){ if(visited[j]==0||(parent[j]==0&&i!=j)){ sum = INT_MAX; } //cout << dist[j] << " "; sum += dist[j]; } //cout << endl; for(int j=1;j<=no_of_input;j++){ //cout << parent[j] << " "; } //cout << sum << endl; ans = min(ans,sum); } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...