# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
861310 | 2023-10-16T02:19:42 Z | nnhzzz | Bosses (BOI16_bosses) | C++14 | 451 ms | 852 KB |
#include<bits/stdc++.h> using namespace std; #define REP(i,a,b) for(int i = (a); i<=(b); ++i) #define REPD(i,a,b) for(int i = (a); i>=(b); --i) #define REPDIS(i,a,b,c) for(int i = (a); i<=(b); i += c) #define task "test" #define task1 "nnhzzz" #define ALL(x) (x).begin(),(x).end() #define SZ(x) (int)(x).size() #define MASK(x) (1LL<<x) #define BIT(x,i) ((x>>i)&1LL) #define vi vector<int> #define vvi vector<vi> #define pii pair<int,int> #define vpii vector<pii> #define fi first #define se second #define ld long double #define ll long long //-------------------------------------------------------------------------------// template<typename T> bool mini(T &a, T b){if(a>b){a=b;return true;}return false;} template<typename T> bool maxi(T &a, T b){if(a<b){a=b;return true;}return false;} //-------------------------------------------------------------------------------// const int MAXN = 5e3+7,N = 1e5+7,inf = 1e9,LOG = 20; const int MOD = 1e9+7,MOD1 = 123456789; //-------------------------------------------------------------------------------// vi adj[MAXN]; void solve(){ int res = inf,n; cin >> n; REP(i,1,n){ int k; cin >> k; while(k--){ int j; cin >> j; adj[j].push_back(i); } } REP(s,1,n){ queue<int> q; q.push(s); vi dep(n+3,0); dep[s] = 1; int ma = 1; while(SZ(q)!=0){ int u = q.front(); q.pop(); REP(i,0,SZ(adj[u])-1){ int v = adj[u][i]; if(dep[v]!=0) continue; dep[v] = dep[u]+1; maxi(ma,dep[v]); q.push(v); } } int sum = 0; REP(i,1,n){ if(dep[i]==0) sum = inf; sum += dep[i]; } mini(res,sum); } cout << res; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } if(fopen(task1".inp","r")){ freopen(task1".inp","r",stdin); freopen(task1".out","w",stdout); } solve(); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 576 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 576 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 344 KB | Output is correct |
8 | Correct | 1 ms | 576 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 1 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 576 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 0 ms | 348 KB | Output is correct |
7 | Correct | 0 ms | 344 KB | Output is correct |
8 | Correct | 1 ms | 576 KB | Output is correct |
9 | Correct | 0 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 4 ms | 604 KB | Output is correct |
13 | Correct | 3 ms | 604 KB | Output is correct |
14 | Correct | 88 ms | 604 KB | Output is correct |
15 | Correct | 18 ms | 604 KB | Output is correct |
16 | Correct | 451 ms | 768 KB | Output is correct |
17 | Correct | 436 ms | 796 KB | Output is correct |
18 | Correct | 444 ms | 852 KB | Output is correct |