제출 #640119

#제출 시각아이디문제언어결과실행 시간메모리
640119dantBosses (BOI16_bosses)C++14
100 / 100
652 ms3544 KiB
#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

컴파일 시 표준 에러 (stderr) 메시지

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...