// //In His Name
// #include <bits/stdc++.h>
// using namespace std;
// #define ll long long
// //#define int ll
// typedef pair<int, int> pii;
// typedef pair<long long, int> pli;
// typedef pair<long long, long long> pll;
// #define F first
// #define S second
// #define bug(x) cout << "Ah shit , here we go again : " << x <<endl
// #define all(x) x.begin() , x.end()
// #define pb push_back
// const int maxn = 5e5 + 10, MOD = 1e9 + 7 , sq = 350;
// const ll INF = 1e18;
// struct hoom{
// int l , r , w , index;
// };
//
// int n , m , c[maxn] , vt[2*maxn] , h[maxn] , st[maxn] , fn[maxn] , t = 1 , cnt[200] ;
// bool mark[maxn];
// string ans[maxn];
// vector<int> adj[maxn];
// vector<hoom> q;
//
// bool cmp(hoom a , hoom b){
// return (a.l/sq != b.l/sq ? a.l < b.l : a.r < b.r);
// }
//
// void dfs(int v , int p){
// h[v] = h[p]+1;
// st[v] = t;
// vt[t] = v;
// t++;
// for(int u : adj[v]) if(u!=p) dfs(u,v);
// fn[v] = t;
// vt[t] = v;
// t++;
// }
//
// int main(){
// ios_base::sync_with_stdio(false);
//
// cin >> n >> m;
// for(int i = 2 ; i <= n ; i++){
// int u ;
// cin >> u;
// adj[u].pb(i);
// adj[i].pb(u);
// }
// string s;
// cin >> s;
// for (int i = 1; i <= n ; ++i) c[i] = int(s[i-1]);
// dfs(1,0);
// for(int i = 1 ; i <= m ; i++){
// int v , k;
// cin >> v >> k;
// q.pb({st[v] , fn[v] , k , i});
// }
// sort(all(q) , cmp);
// int L = 0 , R = 1 , x = 0;
// for(hoom i : q){
// int l = i.l , r = i.r , ind = i.index ;
//
// while(R <= i.r){
// int v = vt[R];
// if(mark[vt[R]]){
// mark[vt[R]] = false;
// }
// else {
// mark[R] = true;
// if (h[vt[R]] == i.w) {
// cnt[c[vt[R]]]++;
// if (cnt[c[vt[R]]] % 2 == 1) x++;
// else x--;
// }
// }
// R++;
// }
// while(L-1 >= i.l){
// L--;
// if(mark[vt[L]]){
// mark[vt[L]] = false;
// continue;
// }
// else mark[vt[L]] = true;
// if(h[vt[L]] == i.w) {
// cnt[c[vt[L]]]--;
// if (cnt[c[vt[L]]] % 2 == 1) x++;
// else x--;
// }
// }
// while(L+1 <= i.l){
// if(mark[vt[L]]){
// mark[vt[L]] = false;
// }
// else {
// mark[vt[L]] = true;
// if (h[vt[L]] == i.w) {
// cnt[c[vt[L]]]++;
// if (cnt[c[vt[L]]] % 2 == 1) x++;
// else x--;
// }
// }
// L++;
// }
// while(R-1 > i.r){
// R--;
// if(mark[vt[R]]){
// mark[vt[R]] = false;
// continue;
// }
// else mark[vt[R]] = true;
// if(h[vt[R]] == i.w) {
// cnt[c[vt[R]]]--;
// if (cnt[c[vt[R]]] % 2 == 1) x++;
// else x--;
// }
// }
// ans[i.index] = (x == 1 or x == 0 ? "YES" : "NO");
// }
// for(int i = 1 ; i <= m ; i++) cout << ans[i] << "\n";
// }
//In His Name
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef pair<long long, int> pli;
typedef pair<long long, long long> pll;
#define ll long long
#define int ll
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
#define ceil(x,y) x/y + min(1,x%y);
const int maxn = 5000 + 10, MOD = 1e9 + 7;
const ll INF = 1e18;
int n , h[maxn] , ans = INF , ians = 1;
vector<int> adj[maxn] , adj2[maxn];
bool mark[maxn];
void dfs(int v){
mark[v] = true;
for(int u : adj2[v]){
if(!mark[u]){
dfs(u);
h[v] += h[u];
}
}
}
main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1 ; i <= n ; i++){
int x;
cin >> x;
for(int u = 1 ; u <= x ; u++){
int y;
cin >> y;
adj[y].pb(i);
}
}
queue<int> q;
for(int i = 1 ; i <= n ; i++){
q.push(i);
mark[i] = true;
while(!q.empty()){
int v = q.front();
q.pop();
for(int u : adj[v]){
if(!mark[u]) {
q.push(u);
mark[u] = true;
h[u] = h[v]+1;
}
}
}
int maxi = -1e9 , ok = 1;
for(int j = 1 ; j <= n ; j++) if(!mark[j]) ok = 0;
for(int j = 1 ; j <= n ; j++){
if(h[j] > maxi) maxi = h[j];
h[j] = 0;
mark[j] = false;
}
if(ok and maxi < ans) ans = maxi , ians = i;
}
memset(mark , false , sizeof mark);
fill(h , h+n+5 , 0);
q.push(ians);
mark[ians] = true;
while(!q.empty()){
int v = q.front();
q.pop();
for(int u : adj[v]){
if(!mark[u]) {
q.push(u);
mark[u] = true;
h[u] = h[v]+1;
adj2[v].pb(u);
adj2[u].pb(v);
}
}
}
memset(mark , false , sizeof mark);
fill(h , h+n+5 , 1);
dfs(ians);
int sum = 0ll;
for(int i = 1 ; i <= n ; i++) sum += h[i];
cout << sum;
}
Compilation message
bosses.cpp:167:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
167 | main(){
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
