이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define int long long
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pi;
const int mod = 1e9 + 9;
const int N = 106 * 106;
const int nax = 1e6+6;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, ans = 2e18;
vector<int> possible_childs[5005];
vector<int> cur_tree[5005];
vector<int> dp(5005, 0);
void dfs(int node, int pre) {
dp[node] = 1;
for(auto it : cur_tree[node]) {
if(it != pre) {
dfs(it, node);
dp[node] += dp[it];
}
}
}
int root(int x) {
queue<int> Q;
Q.push(x);
vector<bool> viz(n + 1, false);
for(int i = 1; i <= n; i++) {
cur_tree[i].clear();
dp[i] = 0;
}
viz[x] = true;
while(Q.size()) {
int node = Q.front();
Q.pop();
for(auto it : possible_childs[node]) {
if(!viz[it]) {
viz[it] = true;
Q.push(it);
cur_tree[node].push_back(it);
}
}
}
for(int i = 1; i <= n; i++) if(!viz[i]) return 2e18;
dfs(x, 0);
int sol = 0;
for(int i = 1; i <= n; i++) {
sol += dp[i];
}
return sol;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
int len;
cin >> len;
for(int j = 1; j <= len; j++) {
int x;
cin >> x;
possible_childs[x].push_back(i);
}
}
for(int i = 1; i <= n; i++) {
ans = min(ans, root(i));
}
cout << ans << '\n';
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
bosses.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
4 | #pragma GCC optimization ("O3")
|
bosses.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
5 | #pragma GCC optimization ("unroll-loops")
|
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |