제출 #483473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483473		Urvuk3	Bosses (BOI16_bosses)	C++17	100 / 100	682 ms	720 KiB

bosses

/*
link:https://oj.uz/problem/view/BOI16_bosses NAPOMENA:isti je zadatak samo je razlika u tome sto nema K
Удружење тенисера
Нова структура ATП (асоцијације тениских професионалаца) у којој ради
програмер Ноле има облик стабла са кореном, тако да сваком чвору дрвета
одговара један тенисер. Неки тенисер се сматра функционером других
тенисера ако је он корен подстабла које садржи друге чворове (наследнике)
којима је он функционер . У новој структури АТП удружења, сваки тенисер је
понудио списак тенисера који он жели да види на месту свог функционера.
Зараде у АТПу се утврђују према следећим захтевима:
    Плата је позитиван цео број, вишеструко већа од званичне минималне зараде и не
мања од званичне минималне зараде;
    Плата сваког функционера мора бити већа од збира зарада његових директних
подређених тенисера.

Напишите програм који прави нову структуру АТПа тако да се сваком тенисеру
додели функционер са списка који је он предложио, а износ плата свих
тенисера буде што мањи.
Улаз
Први ред стандардног уноса садржи две позитивне целобројне
вредности N и K, одвојене размаком (2≤N≤5000, 1≤K≤550).
Број N представља број тенисера, а број K представља минималну зараду.
Тенисери се нумеришу природним бројевима: 1, 2, 3, ..., N. Потом на
стандардном улазу следи N редова који описују списак жеља тенисера.
Ред i садржи цео број ai, праћен списком ai целих бројева. Списак садржи
бројеве тенисера које би i-ти тенисер прихватио као своје функционере
Излаз
У једином реду стандардног излаза приказати најнижи могући укупан износ
плата, међу свим важећим опцијама. Гарантовано је да су улазни подаци
изабрани тако да постоји бар једно решење.
*/

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll MAXN=6e3,MAXA=5e6+5,INF=1e9,LINF=1e18;
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mid (l+r)/2
#define sz(a) int((a).size())
#define all(a) a.begin(),a.end()
#define mod 1000000007LL
#define pb push_back
#define endl "\n"
#define PRINT(x) cerr<<#x<<'-'<<x<<endl<<flush;
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
#define PRINTvec(x) { cerr<<#x<<"-"; for(int i=0;i<sz(x);i++) cerr<<x[i]<<" "; cerr<<endl; }
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

ll n,m,k,q,x,y,z,res=INF,l,r;
string s,t;
vector<int> a;
ifstream input;
ofstream output;
vector<int> adj[MAXN];
vector<ll> dist(MAXN);
vector<bool> visited(MAXN);

#ifdef ONLINE_JUDGE
    #define input cin
    #define output cout
#endif

ll bfs(int x){
    queue<int> q;
    dist[x]=1;
    visited[x]=true;
    q.push(x);
    while(!q.empty()){
        int s=q.front(); q.pop();
        for(auto v:adj[s]){
            if(visited[v]) continue;
            visited[v]=true;
            dist[v]=dist[s]+1;
            q.push(v);
        }
    }
    ll sum=0;
    for(int i=1;i<=n;i++){
        sum+=dist[i];
    }
    for(int i=1;i<=n;i++){
        if(!visited[i]){
            return INF;
        }
    }
    return sum;
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>q;
        for(int j=0;j<q;j++){
            cin>>x;
            adj[x].pb(i);
        }
    }
    for(int i=1;i<=n;i++){
        fill(all(visited),false);
        fill(all(dist),0);
        res=min(res,bfs(i));
    }
    cout<<res<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
        input.open("D:\\UROS\\Programiranje\\input.in",ios::in);
	output.open("D:\\UROS\\Programiranje\\output.out",ios::out|ios::trunc);
    #endif
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33