oj.uz

답안 #549791

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
549791 2022-04-16T14:31:39 Z Soul234 Bosses (BOI16_bosses) C++14
100 / 100
 1355 ms 1056 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}
const ll INF = 1e18;
tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a = b,1 : 0;
}
tcT> bool ckmin(T&a, const T&b) {
    return b < a ? a = b,1 : 0;
}
const int MX = 5e3+5;
vi adj[MX], nadj[MX];
int N, dist[MX];
ll sum[MX], tot;

void dfs(int u) {
    sum[u] = 0;
    each(v, nadj[u]) {
        dfs(v);
        sum[u] += sum[v];
    }
    tot += (++sum[u]);
}

void solve() {
    cin>>N;
    FOR(i,1,N+1) {
        int k; cin>>k;
        while(k--) {
            int u; cin>>u;
            adj[u].pb(i);
        }
    }
    ll ans = INF;
    FOR(i,1,N+1) {
        FOR(i,1,N+1) nadj[i].clear();
        fill(dist, dist+N+1, -1);
        fill(sum, sum+N+1, 0);
        tot = 0;
        queue<int> q; dist[i] = 0;
        q.push(i);
        while(sz(q)) {
            int u = q.front(); q.pop();
            each(v, adj[u]) if(dist[v] == -1) {
                dist[v] = dist[u] + 1;
                nadj[u].pb(v);
                q.push(v);
            }
        }
        bool bad = 0;
        FOR(i,1,N+1) bad |= dist[i] == -1;
        if(bad) continue;
        dfs(i);
        ckmin(ans, tot);
    }
    cout << ans << nl;
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

bosses.cpp: In function 'void setIO(std::string)':
bosses.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bosses.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 564 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 564 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 560 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 564 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 560 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 5 ms 724 KB Output is correct
13 Correct 3 ms 724 KB Output is correct
14 Correct 220 ms 808 KB Output is correct
15 Correct 45 ms 724 KB Output is correct
16 Correct 721 ms 1056 KB Output is correct
17 Correct 1350 ms 984 KB Output is correct
18 Correct 1355 ms 1000 KB Output is correct