| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 640119 |
2022-09-13T16:59:02 Z |
dant |
Bosses (BOI16_bosses) |
C++14 |
|
652 ms |
3544 KB |
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define FORE(i, a) for(auto i : a)
#define FORC(cont, it) for(typeof((cont).begin()) it = (cont).begin(); it != (cont).end(); it++)
#define ull unsigned long long
#define ll long long
#define ld long double
#define clr(v, d) memset(v, d, sizeof(v))
#define vt vector
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define erase_duplicates(x) x.erase(unique(all(x)),x.end());
#define fi first
#define se second
#define deb(x) cout << #x << ": "<< x << '\n';
using namespace std;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<double,double>;
using vi = vt<int>;
using vb = vt<bool>;
using vl = vt<ll>;
using vd = vt<double>;
using vs = vt<string>;
using vpi = vt<pi>;
using vpl = vt<pl>;
using vpd = vt<pd>;
#define lb lower_bound
#define ub upper_bound
template<class T> int lwb(vt<T>& a, const T& b) { return int(lb(all(a),b)-begin(a)); }
template<class T> int upb(vt<T>& a, const T& b) { return int(ub(all(a),b)-begin(a)); }
template <typename T> std::istream& operator>>(std::istream& input, std::vector<T>& data){ for(T& x : data)input >> x;return input;}
template <typename T> std::ostream& operator<<(std::ostream& stream, const vector<T>& vec){ for(size_t i = 0; i < vec.size(); i++){stream << vec[i];if(i != vec.size() - 1)stream << ' ';}; return stream; }
template<class T> bool umin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool umax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int dx[8] = {-1,-1,-1, 0,0, 1,1,1};
const int dy[8] = {-1, 0, 1,-1,1,-1,0,1};
const int d4x[4] = {-1, 0, 0,1};
const int d4y[4] = {0, 1,-1, 0};
const double PI = acos(-1.0);
const int INF = 1e9;
const int INFNEG = INT_MIN;
const ll int MOD = 1e9+7;
const double EP = 1E-10;
bool myCompare(pair<ll,ll> p1, pair<ll,ll> p2){
return p1.se < p2.se || p1.se == p2.se && p1.fi < p2.fi ;
}
const int mxN = 130000 + 10;
vi adj[mxN];
ll n;
ll bfs(int start){
queue<pl> q;
vb vis(mxN,0);
q.push({start,1});
vis[start] = 1;
ll cnt = 0;
ll tot = 0;
while(!q.empty()){
auto now = q.front();
q.pop();
cnt++;
ll node = now.fi;
tot += now.se;
for(auto &neigh: adj[node]){
if(!vis[neigh]){
vis[neigh] = 1;
q.push({neigh,now.se+1});
}
}
}
return (cnt != n ? 1e18 : tot);
}
void solve() {
cin >> n;
FOR(v,0,n){
ll m; cin >> m;
while(m--){
ll u; cin >> u; u--;
adj[u].pb(v);
}
}
ll ans = 1e18;
FOR(i,0,n){
ll curr = bfs(i);
umin(ans,curr);
}
cout<<ans<<'\n';
// string s,t; cin >> s >> t;
// n = sz(s), m = sz(t);
// vi dp(n+1);
// vi dpPrev(n+1);
// FOR(i,1,n+1){
// FOR(j,1,m+1){
// if(s[i-1] == t[j-1]){
// dp[j] = dpPrev[j-1] + 1;
// ans.pb({i-1,j-1});
// cout<<i-1<<" "<<j-1<<'\n';
// }
// else{
// dp[j] = max(dp[j-1],dpPrev[j]);
// }
// }
// swap(dp,dpPrev);
// }
// cout<<dpPrev[n]<<'\n';
// // reverse(all(ans));
// FOR(j,2,sz(ans)){
// auto i = ans[j];
// cout<<i.fi<<" "<<i.se<<'\n';
// }
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t = 1, i = 0;
// cin >> t;
while (t--){
// cout<<"Case "<<++i<<": ";
solve();
}
}
/*
*/
// se vuelve más fácil
// cada día es un poco más fácil, pero tienes que hacerlo cada día
// esa es la parte difícil, pero se vuelve más fácil
Compilation message
bosses.cpp: In function 'bool myCompare(std::pair<long long int, long long int>, std::pair<long long int, long long int>)':
bosses.cpp:56:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
56 | return p1.se < p2.se || p1.se == p2.se && p1.fi < p2.fi ;
| ^
bosses.cpp: In function 'int main()':
bosses.cpp:137:16: warning: unused variable 'i' [-Wunused-variable]
137 | int t = 1, i = 0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 5 |
Correct |
1 ms |
3284 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 5 |
Correct |
1 ms |
3284 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 7 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 8 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 9 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 10 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 11 |
Correct |
2 ms |
3284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 5 |
Correct |
1 ms |
3284 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 7 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 8 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 9 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 10 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 11 |
Correct |
2 ms |
3284 KB |
Output is correct |
| 12 |
Correct |
6 ms |
3412 KB |
Output is correct |
| 13 |
Correct |
5 ms |
3412 KB |
Output is correct |
| 14 |
Correct |
143 ms |
3452 KB |
Output is correct |
| 15 |
Correct |
6 ms |
3412 KB |
Output is correct |
| 16 |
Correct |
506 ms |
3540 KB |
Output is correct |
| 17 |
Correct |
652 ms |
3540 KB |
Output is correct |
| 18 |
Correct |
651 ms |
3544 KB |
Output is correct |
