oj.uz

답안 #522742

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
522742 2022-02-05T15:12:18 Z nikolapesic2802 Bosses (BOI16_bosses) C++14
100 / 100
 1196 ms 1192 KB 
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
ll n, mini;
vector<ll> graf[5010], detsa[5010];
bool pos[5010];
ll uk;
void bfs(ll poc) {
    queue<ll> q;
    pos[poc]=true;
    q.emplace(poc);
    while(!q.empty()) {
        ll tren=q.front(); q.pop();
        for(auto adj:graf[tren]) {
            if(pos[adj]) continue;
            pos[adj]=true;
            q.emplace(adj);
            detsa[tren].push_back(adj);
        }
    }
}
ll racunaj(ll node) {
    ll suma=1LL;
    for(auto dete:detsa[node]) {
        suma+=racunaj(dete);
    }
    uk+=suma;
    return suma;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    mini=2000000000000000LL;
    cin >> n;
    for(ll i=1; i<=n; ++i) {
        ll k; cin >> k;
        while(k--) {
            ll x; cin >> x;
            graf[x].push_back(i);
        }
    }
    for(ll root=1; root<=n; ++root) {
        for(ll i=1; i<=n; ++i) pos[i]=false;
        for(ll i=1; i<=n; ++i) detsa[i].clear();
 
        uk=0LL;
        bfs(root);
        racunaj(root);
      bool ok=1;
      for(int i=1;i<=n;i++)
        if(!pos[i])
          ok=0;
      if(ok)
        mini=min(mini, uk);
    }
    cout << mini;
    return 0;
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 556 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 556 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 4 ms 716 KB Output is correct
13 Correct 3 ms 844 KB Output is correct
14 Correct 294 ms 816 KB Output is correct
15 Correct 41 ms 764 KB Output is correct
16 Correct 946 ms 1192 KB Output is correct
17 Correct 1196 ms 964 KB Output is correct
18 Correct 1161 ms 920 KB Output is correct