# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
489808 | 2021-11-24T18:27:47 Z | ala2 | Bosses (BOI16_bosses) | C++14 | 13 ms | 23988 KB |
#include <bits/stdc++.h> #define int long long using namespace std; vector<int>v[1001000]; int vi[5010][5010]; int d[5050][5050]; vector<int>gr[5050]; int dfs(int node,int i) { if(d[i][node]) return d[i][node]; if(gr[node].size()==0) { return d[i][node]=1;; } int sum=0; for(int u=0;u<gr[node].size();u++) { sum+=dfs(gr[node][u],i); } return d[i][node]=sum+1; } signed main() { // memset(gr,0,sizeof gr); int n; cin>>n; for(int i=0;i<n;i++) { int k; cin>>k; for(int j=0;j<k;j++) { int x; cin>>x; v[x].push_back(i+1); } } int mn=100000000000000000; for(int i=1;i<n+1;i++) { //cout<<"_______________________"<<endl; for(int uu=0;uu<=n;uu++) { gr[uu].clear(); } queue<int>q; q.push(i); vi[i][i]=1; while(!q.empty()) { int x=q.front(); q.pop(); for(int j=0;j<v[x].size();j++) { int h=v[x][j]; if(!vi[i][h]) { vi[i][h]=1; q.push(h); // cout<<" "<<i<<" "<<h<<endl; gr[x].push_back(h); } } } int c=dfs(i,i); int yy=0; for(int j=1;j<=n;j++) { // // cout<<" "<<i<<" "<<j<<" "<<d[i][j]<<endl; yy+=d[i][j]; } // cout<<" "<<i<<" "<<yy<<endl; mn=min(mn,yy); } cout<<mn<<endl; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 23884 KB | Output is correct |
2 | Correct | 12 ms | 23892 KB | Output is correct |
3 | Incorrect | 13 ms | 23988 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 23884 KB | Output is correct |
2 | Correct | 12 ms | 23892 KB | Output is correct |
3 | Incorrect | 13 ms | 23988 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 23884 KB | Output is correct |
2 | Correct | 12 ms | 23892 KB | Output is correct |
3 | Incorrect | 13 ms | 23988 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |