제출 #107394

#제출 시각아이디문제언어결과실행 시간메모리
107394aryamanBosses (BOI16_bosses)C++14
0 / 100
2 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()); ll bfs(int s, vector<vi> &g) { vector<bool> vis(g.size()); queue<ii> bfs; bfs.push({s, 0}); ll res = 0; while (!bfs.empty()) { ii u = bfs.front(); bfs.pop(); res += u.s + 1; vis[u.f] = true; for (auto &v : g[u.f]) { if (vis[v]) continue; bfs.push({v, u.s + 1}); vis[v] = true; } } return res; } 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(); for (int i = 0; i < n; i++) { ans = min(ans, bfs(i, g)); } 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...