oj.uz

답안 #780958

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
780958 2023-07-12T15:03:10 Z 1075508020060209tc Bosses (BOI16_bosses) C++14
100 / 100
 1018 ms 15056 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;
vector<int>pch[200005];
vector<int>pfa[200005];
vector<int>e[200005];
int dp[200005];
int vis[200005];
int ans;

void dfs(int nw){
dp[nw]=1;
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i];
    dfs(v);
    dp[nw]+=dp[v];
}
}

void solve(int rt){
for(int i=1;i<=n;i++){
    vis[i]=0;
    dp[i]=0;
    e[i].clear();
}
vis[rt]=1;
queue<int>q;
q.push(rt);
while(q.size()){
    int nw=q.front();
    q.pop();
    for(int i=0;i<pch[nw].size();i++){
        int v=pch[nw][i];
        if(vis[v]){continue;}
        e[nw].push_back(v);
        vis[v]=1;
        q.push(v);
    }
}
for(int i=1;i<=n;i++){
    if(vis[i]==0){return;}
}
dfs(rt);
int cal=0;
for(int i=1;i<=n;i++){
    cal+=dp[i];
}
ans=min(ans,cal);
}


signed main(){
cin>>n;
for(int i=1;i<=n;i++){
    int k;
    cin>>k;
    for(int j=1;j<=k;j++){
        int v;
        cin>>v;
        pfa[i].push_back(v);
        pch[v].push_back(i);
    }
}
ans=1e18;
for(int i=1;i<=n;i++){
    solve(i);
}
cout<<ans<<endl;

}

Compilation message

bosses.cpp: In function 'void dfs(long long int)':
bosses.cpp:16:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
bosses.cpp: In function 'void solve(long long int)':
bosses.cpp:35:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0;i<pch[nw].size();i++){
      |                 ~^~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14400 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Correct 7 ms 14292 KB Output is correct
4 Correct 7 ms 14292 KB Output is correct
5 Correct 8 ms 14336 KB Output is correct
6 Correct 7 ms 14292 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14400 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Correct 7 ms 14292 KB Output is correct
4 Correct 7 ms 14292 KB Output is correct
5 Correct 8 ms 14336 KB Output is correct
6 Correct 7 ms 14292 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 8 ms 14404 KB Output is correct
9 Correct 9 ms 14292 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 7 ms 14400 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14400 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Correct 7 ms 14292 KB Output is correct
4 Correct 7 ms 14292 KB Output is correct
5 Correct 8 ms 14336 KB Output is correct
6 Correct 7 ms 14292 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 8 ms 14404 KB Output is correct
9 Correct 9 ms 14292 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 7 ms 14400 KB Output is correct
12 Correct 12 ms 14664 KB Output is correct
13 Correct 11 ms 14804 KB Output is correct
14 Correct 162 ms 14980 KB Output is correct
15 Correct 50 ms 14840 KB Output is correct
16 Correct 638 ms 15056 KB Output is correct
17 Correct 1018 ms 15004 KB Output is correct
18 Correct 1002 ms 15012 KB Output is correct