oj.uz

Submission #483473

# Submission time Handle Problem Language Result Execution time Memory
483473 2021-10-29T19:49:39 Z Urvuk3 Bosses (BOI16_bosses) C++17
100 / 100
 682 ms 720 KB 
/*
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.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 480 KB Output is correct
9 Correct 1 ms 508 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 5 ms 588 KB Output is correct
13 Correct 3 ms 572 KB Output is correct
14 Correct 146 ms 608 KB Output is correct
15 Correct 13 ms 588 KB Output is correct
16 Correct 501 ms 688 KB Output is correct
17 Correct 682 ms 716 KB Output is correct
18 Correct 668 ms 720 KB Output is correct