# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
42378 | 2018-02-26T15:12:50 Z | Hassoony | Bosses (BOI16_bosses) | C++11 | 1500 ms | 1612 KB |
#include<bits/stdc++.h> #include<unordered_map> #define F first #define S second using namespace std; typedef long long ll; typedef long double D; const ll inf=(1ll<<61); const ll mod=1e9+7; const int MX=5009; int n,k,x,vis[MX],val[MX]; vector<int>v[MX],v1[MX]; ll ans,mn=inf; void dfs(int x){ if(v1[x].size()==0){ val[x]=1; ans++; vis[x]=1; return; } if(vis[x])return; vis[x]=1; int &ret=val[x]; for(auto pp:v1[x]){ if(vis[pp])continue; dfs(pp); ret+=val[pp]; } ++ret; ans+=ret; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&k); while(k--){ scanf("%d",&x); v[x].push_back(i); } } for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); memset(val,0,sizeof(val)); for(int j=1;j<=n;j++)v1[j].clear(); ans=0; queue<int>q; q.push(i); while(!q.empty()){ int x=q.front();q.pop(); vis[x]=1; for(auto pp:v[x]){ if(vis[pp])continue; v1[x].push_back(pp); vis[pp]=1; q.push(pp); } } memset(vis,0,sizeof(vis)); dfs(i); bool b=1; for(int j=1;j<=n;j++){ if(!vis[j])b=0; } if(b)mn=min(mn,ans); } printf("%lld\n",mn); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 608 KB | Output is correct |
3 | Correct | 2 ms | 660 KB | Output is correct |
4 | Correct | 2 ms | 664 KB | Output is correct |
5 | Correct | 2 ms | 668 KB | Output is correct |
6 | Correct | 2 ms | 856 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 608 KB | Output is correct |
3 | Correct | 2 ms | 660 KB | Output is correct |
4 | Correct | 2 ms | 664 KB | Output is correct |
5 | Correct | 2 ms | 668 KB | Output is correct |
6 | Correct | 2 ms | 856 KB | Output is correct |
7 | Correct | 2 ms | 856 KB | Output is correct |
8 | Correct | 2 ms | 856 KB | Output is correct |
9 | Correct | 2 ms | 1020 KB | Output is correct |
10 | Correct | 3 ms | 1020 KB | Output is correct |
11 | Correct | 3 ms | 1020 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 504 KB | Output is correct |
2 | Correct | 2 ms | 608 KB | Output is correct |
3 | Correct | 2 ms | 660 KB | Output is correct |
4 | Correct | 2 ms | 664 KB | Output is correct |
5 | Correct | 2 ms | 668 KB | Output is correct |
6 | Correct | 2 ms | 856 KB | Output is correct |
7 | Correct | 2 ms | 856 KB | Output is correct |
8 | Correct | 2 ms | 856 KB | Output is correct |
9 | Correct | 2 ms | 1020 KB | Output is correct |
10 | Correct | 3 ms | 1020 KB | Output is correct |
11 | Correct | 3 ms | 1020 KB | Output is correct |
12 | Correct | 7 ms | 1076 KB | Output is correct |
13 | Correct | 6 ms | 1112 KB | Output is correct |
14 | Correct | 401 ms | 1376 KB | Output is correct |
15 | Correct | 63 ms | 1376 KB | Output is correct |
16 | Correct | 1317 ms | 1612 KB | Output is correct |
17 | Execution timed out | 1551 ms | 1612 KB | Time limit exceeded |
18 | Halted | 0 ms | 0 KB | - |