Submission #695219

#	Time	Username	Problem	Language	Result	Execution time	Memory
695219		HossamHero7	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	212 KiB

bosses

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define endl '\n'
vector<vector<int>> v;
vector<vector<bool>> vis;
vector<vector<int>> adj;
int n;
int root=-1;
ll ans=1e18;
vector<ll> sub;
ll anss=0;
void dfs(int node,int par){
    ll x = 0;
    for(auto ch : adj[node]){
        if(ch == par) continue;
        dfs(ch,node);
        x += sub[ch];
    }
    sub[node] = x+1;
    anss += sub[node];
    sub[node] = x + sub[node];
}
void solve(int i){
    if(i == n+1 && root != -1){
        bool check = 0;
        for(auto j : vis[root]) check |= j;
        if(!check) return;
        /*for(int z=1;z<=n;z++){
            for(auto ch : adj[z]) cout<<z<<" "<<ch<<endl;
        }*/
        queue<int> q;
        q.push(root);
        vector<int> par(n+1);
        vector<int> leaves;
        while(q.size()){
            int cur = q.front();        q.pop();
            for(auto ch : adj[cur]){
                q.push(ch);
                par[ch] = cur;
            }
            if(adj[cur].size() == 0) leaves.push_back(cur);
        }
        dfs(root,0);
        ans = min(ans,anss);
       /* for(int j=1;j<=n;j++) cout<<sub[j]<<' ';
        cout<<endl;
        cout<<anss<<endl;
        cout<<endl;*/
        anss = 0;
        return;
    }
    else if(i == n+1){
        return;
    }
    for(auto j : v[i]){
        if(vis[i][j]) continue;
        vis[i][j] = 1;
        vis[j][i] = 1;
        adj[j].push_back(i);
        solve(i+1);
        vis[i][j] = 0;
        vis[j][i] = 0;
        adj[j].pop_back();
    }
    if(root == -1){
        root = i;
        solve(i+1);
        root = -1;
    }
}
void solve(){
    cin>>n;
    v.resize(n+1);
    for(int i=0;i<n;i++){
        int k;cin>>k;
        v[i+1].resize(k);
        for(auto &j:v[i+1]) cin>>j;
    }
    vis.resize(n+1,vector<bool>(n+1));
    adj.resize(n+1);
    sub.resize(n+1);
    solve(1);
    cout<<ans-1<<endl;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

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