oj.uz

답안 #754293

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
754293 2023-06-07T12:20:34 Z emad234 Bosses (BOI16_bosses) C++17
0 / 100
 1 ms 332 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -