Submission #330270

#TimeUsernameProblemLanguageResultExecution timeMemory
330270Ruba_KBosses (BOI16_bosses)C++14
0 / 100
1 ms492 KiB
#include<bits/stdc++.h> using namespace std; #define debug(x) cout << '[' << #x << " is: " << x << "] " << endl; #define imod(a , n) (a % n + n ) % n #define fastio ios_base::sync_with_stdio(false);cin.tie(0); #define inF freopen("file.txt","r",stdin ); #define outF freopen("perimeter.out" , "w" , stdout ) ; #define sor(v) sort(v.begin() , v.end()); #define print(v) for(auto f : v ) cout << f << " " ; #define rsor(v) sort(v.rbegin() , v.rend()); #define rev(v) reverse(v.begin() , v.end()); #define ll long long //#define int ll #define pii pair<int , int > const int N = 5e3 + 5 , M = N * 4 ; const ll MOD = 1e9 + 7 , oo = 1e9 , OO = 1e18 ; //37 int di[] = {1 , -1 , 0 , 0}; int dj[] = {0 , 0 , 1 , -1}; int n ; stack<int>all ; vector<vector<int> > sz ; vector<int> adj[N]; int arr[N] , vis[N] , vid; void bfs(int p){ vis[p] = vid ; queue<int>q ; q.push(p); while(q.size()){ int fr = q.front(); q.pop(); all.push(fr); for(auto f : adj[fr]){ if(vis[f] == vid) continue ; q.push(f); vis[f] = vid ; sz[fr].push_back(f); } } } int32_t main() { // inF; // inF;outF; fastio; // Dont Forget memset cin >> n ; for(int i = 1 ; i <= n ; i ++){ int k ; cin >> k; while(k--){ int a ; cin >> a; adj[a].push_back(i); } } int mn = oo ; for(int i = 1; i <= n ; i ++){ vid ++ ; sz.clear(); sz.resize(n + 1); memset(arr , 0 , sizeof arr); bfs(i); int sum = 0 ; while(all.size()){ int tp = all.top(); all.pop(); int c = 0; for(auto f : sz[tp]){ c += arr[f]; } arr[tp] = c + 1 ; sum += (c + 1); } mn = min(mn , sum); } cout << mn ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...