oj.uz

답안 #975557

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
975557 2024-05-05T13:22:43 Z dong_gas Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 9668 KB 
#include <bits/extc++.h>
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
 
int n, ans=1e18;
queue<int> v[5050], hubo[5050];
vector<int> adj[5050];
int a[5050];

void dfs(int u) {
    a[u]=1;
    for(int& v:adj[u]) {
        dfs(v);
        a[u]+=a[v];
    }
}

int f(int r) {
    for(int i=1;i<=n;i++) adj[i].clear(), hubo[i]=v[i], a[i]=0;
    vector<bool> visited(n+1,0);
    queue<int> q;
    q.push(r);
    visited[r]=1;
    while(!q.empty()) {
        int u=q.front(); q.pop();
        while(!hubo[u].empty()) {
            int v=hubo[u].front(); hubo[u].pop();
            if(visited[v]) continue;
            visited[v]=1;
            adj[u].push_back(v);
            q.push(v);
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++) if(visited[i]) cnt++;
    if(cnt<n) return 1e18;
    dfs(r);
    return accumulate(a+1,a+n+1,0);
}

void solve() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        int k; cin>>k;
        while(k --> 0) {
            ll x; cin>>x;
            v[x].push(i);
        }
    }
    for(int r=1;r<=n;r++) {
        ans=min(ans,f(r));
        //cout<<f(r)<<endl;
    }
    cout<<ans;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc=1; //cin>>tc;
    while(tc --> 0) solve();
}

Compilation message

bosses.cpp:8:12: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    8 | int n, ans=1e18;
      |            ^~~~
bosses.cpp: In function 'int f(int)':
bosses.cpp:39:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   39 |     if(cnt<n) return 1e18;
      |                      ^~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7256 KB Output is correct
2 Correct 4 ms 7260 KB Output is correct
3 Correct 3 ms 7260 KB Output is correct
4 Correct 4 ms 7256 KB Output is correct
5 Correct 4 ms 7376 KB Output is correct
6 Correct 4 ms 7260 KB Output is correct
7 Correct 4 ms 7256 KB Output is correct
8 Correct 4 ms 7260 KB Output is correct
9 Correct 4 ms 7260 KB Output is correct
10 Correct 5 ms 7260 KB Output is correct
11 Correct 5 ms 7336 KB Output is correct
12 Correct 12 ms 7516 KB Output is correct
13 Correct 8 ms 7516 KB Output is correct
14 Correct 1174 ms 9060 KB Output is correct
15 Correct 651 ms 8784 KB Output is correct
16 Execution timed out 1539 ms 9668 KB Time limit exceeded
17 Halted 0 ms 0 KB -