oj.uz

답안 #975571

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
975571 2024-05-05T13:33:14 Z dong_gas Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 9576 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=1e9, p, R;
queue<int> v[5050], hubo[5050];
vector<int> adj[5050];

int dfs(int u) {
    int ret=1;
    for(int& v:adj[u]) ret+=dfs(v);
    //cout<<u<<' '<<ret<<endl;
    if(u!=R) p+=ret;
    return ret;
}

int f(int r) {
    R=r;
    for(int i=1;i<=n;i++) adj[i].clear(), hubo[i]=v[i];
    vector<bool> visited(n+1,0);
    queue<int> q;
    q.push(r);
    visited[r]=1;
    int cnt=0;
    p=0;
    while(!q.empty()) {
        int u=q.front(); q.pop();
        cnt++;
        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);
        }
    }    
    //cout<<cnt<<endl;
    if(cnt<n) return 1e9;
    return dfs(r)+p;
}

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();
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7260 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 4 ms 7260 KB Output is correct
4 Correct 4 ms 7256 KB Output is correct
5 Correct 4 ms 7260 KB Output is correct
6 Correct 3 ms 7260 KB Output is correct
7 Correct 5 ms 7340 KB Output is correct
8 Correct 4 ms 7260 KB Output is correct
9 Correct 4 ms 7260 KB Output is correct
10 Correct 4 ms 7260 KB Output is correct
11 Correct 6 ms 7260 KB Output is correct
12 Correct 12 ms 7476 KB Output is correct
13 Correct 10 ms 7512 KB Output is correct
14 Correct 1118 ms 8720 KB Output is correct
15 Correct 664 ms 8972 KB Output is correct
16 Execution timed out 1535 ms 9576 KB Time limit exceeded
17 Halted 0 ms 0 KB -