Submission #140220

#	Time	Username	Problem	Language	Result	Execution time	Memory
140220		path	Bosses (BOI16_bosses)	C++14	0 / 100	1553 ms	632 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long int ll;
const int N=5e3+5;
int n,k,c[N],p[N],lft,alcz[N],t,isp[N];
ll ans;
vector <int> alc[N],alp[N];
void upd(int ind, int val){
    c[ind]+=val;
    if(p[ind]==-1)
        return;
    upd(p[ind],val);
    return ;
}
int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    memset(p,-1,sizeof p);
    cin>>n;
    lft=n-1;
    for(int i=0;i<n;i++){
        cin>>k;
        while(k--){
            cin>>t;
            alp[i+1].push_back(t);
            alc[t].push_back(i+1);
            alcz[t]++;
        }
    }
    while(lft>0){
        priority_queue< pair<int,int> > q;
        for(int i=0;i<n;i++)
            q.push(make_pair(alcz[i+1],i+1));
        pair<int,int> tmp=q.top();
        lft-=tmp.f;
        t=0;
        for(int i=0;i<alc[tmp.s].size();i++){
            if(~p[alc[tmp.s][i]]) continue;
            c[alc[tmp.s][i]]=max(c[alc[tmp.s][i]],1);
            t+= (c[alc[tmp.s][i]]* (isp[alc[tmp.s][i]]+1) );
            p[alc[tmp.s][i]]=tmp.s;
            for(int j=0;j<alp[alc[tmp.s][i]].size();j++)
                alcz[alp[alc[tmp.s][i]][j]]--;
        }
        isp[tmp.s]=1;
        upd(tmp.s,t-(c[tmp.s]==1));
    }
    for(int i=0;i<=n;i++) ans+=c[i];
    cout<<ans<<'\n';
    /*for(int i=1;i<=n;i++)
        cout<<p[i]<<" "<<c[i]<<'\n';*/
	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<alc[tmp.s].size();i++){
                     ~^~~~~~~~~~~~~~~~~~
bosses.cpp:44:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<alp[alc[tmp.s][i]].size();j++)
                         ~^~~~~~~~~~~~~~~~~~~~~~~~~~

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