oj.uz

Submission #350838

# Submission time Handle Problem Language Result Execution time Memory
350838 2021-01-19T08:48:45 Z MHNaderi Bosses (BOI16_bosses) C++14
100 / 100
 865 ms 1020 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define all(x) x.begin() , x.end()
#define file_init freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define random_init mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
const int maxn=1e4,INF=1e18;
int dis[maxn],mark[maxn],cntd[maxn];
vector<int> m[maxn];
inline int BFS(int u,int n){
    queue<int> q;
    q.push(u);
    mark[u]=1;
    dis[u]=1;
    cntd[dis[u]]=1;
    int mx=0;
//    cout<<"####"<<u<<"####"<<'\n';
    while(q.size()){
        u=q.front();
        for(int v : m[u]){
            if(!mark[v]){
                dis[v]=dis[u]+1;
                cntd[dis[v]]++;
                mark[v]=1;
                q.push(v);
            }
        }
        mx=dis[u];
        q.pop();
    }
    int ans=0,sum=0;
    for(int i=mx;i>0;i--){
        sum+=cntd[i];
        ans+=sum;
//        cout<<i<<" "<<cntd[i]<<'\n';
    }
    int cnt=0;
    for(int i=0;i<=n;i++){
        if(mark[i]) cnt++;
        dis[i]=cntd[i]=mark[i]=0;
    }
    if(cnt<n) return -1;
    return ans;
}
int mk[maxn];
void DFS(int u){
    mk[u]=1;
    for(int v : m[u]){
        if(!mk[v]) DFS(v);
    }
}
int32_t main(){
	ios_base::sync_with_stdio(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
        int k; cin>>k;
        for(int j=0;j<k;j++){
            int x; cin>>x;
            m[x].pb(i);
        }
	}
    int ans=INF;
    for(int i=1;i<=n;i++){
        int x=BFS(i,n);
        if(x!=-1)
        ans=min(ans,x);
    }
    cout<<(ans==INF ? -1 : ans);
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 768 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 768 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 768 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 768 KB Output is correct
12 Correct 5 ms 748 KB Output is correct
13 Correct 4 ms 748 KB Output is correct
14 Correct 210 ms 856 KB Output is correct
15 Correct 44 ms 864 KB Output is correct
16 Correct 755 ms 944 KB Output is correct
17 Correct 865 ms 1020 KB Output is correct
18 Correct 859 ms 1004 KB Output is correct