이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
#define int long long
signed main () {
int n, mn = 1e9;
cin >> n;
vector <int> g[n];
vector <pair <int,int>> edge;
for(int i = 0; i < n; i ++) {
int sz;
cin >> sz;
while(sz --) {
int v;
cin >> v;
g[v-1].push_back(i);
}
}
queue <int> q;
for(int i = 0; i < n; i ++) {
vector <int> dist(n, 1e9);
dist[i] = 0;
q.push(i);
vector <pair <int,int>> temp;
while(!q.empty()) {
int v = q.front();
q.pop();
for(auto u : g[v]) {
if(dist[u] == 1e9) {
temp.push_back({v, u});
dist[u] = dist[v] + 1;
q.push(u);
}
}
}
if(*max_element(dist.begin(), dist.end()) < mn) {
mn = *max_element(dist.begin(), dist.end());
edge = temp;
}
}
for(auto &i : g) i.clear();
for(auto i : edge) g[i.first].push_back(i.second);
vector <int> dp(n, 0);
function <void(int,int)> dfs=[&](int v, int p) {
dp[v] ++;
for(auto u : g[v]) {
if(u == p) continue;
dfs(u, v);
dp[v] += dp[u];
}
};
int root = edge[0].first;
dfs(root, -1);
cout << accumulate(dp.begin(), dp.end(), 0);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |