# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
791081 | 2023-07-23T11:50:07 Z | AndiR | Bosses (BOI16_bosses) | C++14 | 964 ms | 652 KB |
#include <iostream> #include <fstream> #include <vector> #include <queue> using namespace std; ifstream fin ("bos.in"); ofstream fout ("bos.out"); typedef long long ll; const int Nmax=5000; int n; bool vis[Nmax]; vector <pair<int, bool>> ad[Nmax]; queue <int> q; ll sol, mn=(ll)99999999999999999; int dfs(int nod){ int s=1; for (int i=0; i<ad[nod].size(); i++){ if (ad[nod][i].second==1){ ad[nod][i].second=0; s+=dfs(ad[nod][i].first); } } sol+=s; return s; } int main() { cin>>n; int m, a; for (int i=0; i<n; i++){ cin>>m; for (int j=0; j<m; j++){ cin>>a; a--; ad[a].push_back({i, 0}); } } for (int i=0; i<n; i++){ sol=0; vis[i]=1; q.push(i); while (!q.empty()){ for (int j=0; j<ad[q.front()].size(); j++){ if (vis[ad[q.front()][j].first]==0){ q.push(ad[q.front()][j].first); vis[ad[q.front()][j].first]=1; ad[q.front()][j].second=1; } } q.pop(); } bool ok=1; for (int i=0; i<n; i++){ if (vis[i]==0) ok=0; vis[i]=0; } dfs(i); if (sol<mn && ok) mn=sol; } cout<<mn; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 352 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 436 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 352 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 436 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 440 KB | Output is correct |
8 | Correct | 1 ms | 436 KB | Output is correct |
9 | Correct | 1 ms | 436 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 352 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 436 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 440 KB | Output is correct |
8 | Correct | 1 ms | 436 KB | Output is correct |
9 | Correct | 1 ms | 436 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 9 ms | 596 KB | Output is correct |
13 | Correct | 7 ms | 636 KB | Output is correct |
14 | Correct | 192 ms | 652 KB | Output is correct |
15 | Correct | 16 ms | 564 KB | Output is correct |
16 | Correct | 919 ms | 648 KB | Output is correct |
17 | Correct | 964 ms | 644 KB | Output is correct |
18 | Correct | 961 ms | 596 KB | Output is correct |