제출 #107392

#제출 시각아이디문제언어결과실행 시간메모리
107392aryamanBosses (BOI16_bosses)C++14
0 / 100
3 ms384 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> ii; typedef tuple<int, int, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<ld> vd; typedef vector<ll> vl; typedef set<int> si; typedef set<ii> sii; typedef set<ld> sd; typedef set<ll> sl; typedef map<int, int> mii; typedef priority_queue<int> pqi; typedef queue<int> qi; #define mp make_pair #define pb push_back #define f first #define s second mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count()); void dfs(int u, vl &cost, vector<bool> &vis, vector<vi> &g) { vis[u] = true; ll sum = 0; for (auto &v : g[u]) { if (vis[v]) continue; dfs(v, cost, vis, g); sum += cost[v]; } cost[u] = sum + 1; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<vi> g(n); for (int i = 0; i < n; i++) { int m; cin >> m; while (m--) { int j; cin >> j, j--; g[j].push_back(i); } } ll ans = numeric_limits<ll>::max(); vl cost(n); vector<bool> vis(n, false); for (int i = 0; i < n; i++) { dfs(i, cost, vis, g); ll res = 0; for (auto &x : cost) res += x; ans = min(ans, res); fill(vis.begin(), vis.end(), false); } cout << ans << endl; } /* USE LONG LONG!!!! 1 1 2 4 1 2 2 3 2 2 2 2 :pray: :fishy15: :pray: :summitosity: :pray: :prodakcin: .= , =. _ _ /'/ )\,/,/(_ \ \ `//-.| ( ,\\)\//\)\/_ ) | //___\ `\\\/\\/\/\\///' / ,-"~`-._ `"--'_ `"""` _ \`'"~-,_ \ `-. '_`. .'_` \ ,-"~`/ `.__.-'`/ (-\ /-) |-.__,' || | \O) /^\ (O/ | . <- BESSIE THE COW `\\ | / `\ / \\ \ / `\ / `\\ `-. /' .---.--.\ `\\/`~(, '() (' /(O) \\ _,.-.,_) // \\ `\'` / / | || `""""~"` /' |__|| `o */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...