Submission #754293

#	Time	Username	Problem	Language	Result	Execution time	Memory
754293		emad234	Bosses (BOI16_bosses)	C++17	0 / 100	1 ms	332 KiB

bosses

#include <bits/stdc++.h>
#define all(v) ((v).begin(),(v).end())
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const ll mxN = 2e6 + 1;
vector<vector<ll>>eg;
bool vis[mxN];
ll ans;
ll dist[mxN];
signed main()
{
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  ll n;
  cin >>n;
  eg.resize(n + 1);
  ll st = 0,mx = 0;
  for(ll i = 1;i <= n;i++){
    dist[i] = 1;
    ll m;cin >>m;
    for(ll j = 1;j <= m;j++){
      ll x;
      cin >>x;
      eg[x].push_back(i);
      // cout<<x<<' '<<eg[x].size()<<'\n';
      if(eg[x].size() > mx){
        mx = eg[x].size();
        st = x;
      }
    }
  }
  queue<pair<ll,ll>>q;
  stack<pair<ll,ll>>s;
  q.push({st,0});
  while(q.size()){
    auto u = q.front();
    q.pop();
    s.push(u);
    vis[u.first] = 1;
    for(auto x : eg[u.first]){
      if(!vis[x]){
        q.push({x,u.first});
        vis[x] = 1;
      }
    }
  }
  while(s.size()){
    auto u = s.top();
    // cout<<u.first<<' '<<dist[u.first]<<'\n';
    s.pop();
    ans += dist[u.first];
    dist[u.second] += dist[u.first];
  }
  cout <<ans;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:26:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   26 |       if(eg[x].size() > mx){
      |          ~~~~~~~~~~~~~^~~~

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