oj.uz

Submission #243687

# Submission time Handle Problem Language Result Execution time Memory
243687 2020-07-01T14:37:19 Z kimbj0709 Bosses (BOI16_bosses) C++14
100 / 100
 1381 ms 1784 KB 
#pragma optimizaiton("O3");
#include <bits/stdc++.h>
using namespace std;
#define maxn 5050
vector<vector<int> > adj(maxn);
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int no_of_input,no_of_input1,input;
  cin >> no_of_input;
  for(int i=1;i<=no_of_input;i++){
    cin >> no_of_input1;
    for(int j=0;j<no_of_input1;j++){
      cin >> input;
      //adj[i].push_back(input);
      adj[input].push_back(i);
    }
  }
  int ans = INT_MAX;
  deque<pair<int,int> > q1;
  vector<int> dist(maxn,INT_MAX);
  vector<int> parent(maxn,0);
  vector<int> dist2(maxn,0);
  vector<vector<int> > pos(maxn);
  for(int i=1;i<=no_of_input;i++){//tree rooted at node i
    for(int j=0;j<=no_of_input;j++){
      dist[j] = INT_MAX;
      parent[j] = 0;
      dist2[j] = 1;
      pos[j].clear();
    }
    q1.push_back({i,0});
    dist[i] = 0;
    while(q1.size()!=0){
      pair<int,int> a = q1.front();
      q1.pop_front();
      for(auto k:adj[a.first]){
        if(a.second+1<dist[k]){
          dist[k] = a.second+1;
          parent[k] = a.first;
          q1.push_back({k,dist[k]});
        }
      }
    }
    int sum = 0;
    for(int j=1;j<=no_of_input;j++){
      if(j!=i&&parent[j]==0){
        goto cont;
      }
      pos[dist[j]].push_back(j);
    }
    for(int j=no_of_input;j>=0;j--){
      for(auto k:pos[j]){
        dist2[parent[k]] += dist2[k];
      }
    }
    for(int j=1;j<=no_of_input;j++){
      
      if(i!=j&&parent[j]==0){
        sum = 1000000000;
      }
      //cout << dist2[j] << " ";
      sum += dist2[j];
    }
    //cout << endl;
    //cout << sum << "--\n";
    ans = min(ans,sum);
    cont : ;
  }
  cout << ans;
}

Compilation message

bosses.cpp:1:0: warning: ignoring #pragma optimizaiton  [-Wunknown-pragmas]
 #pragma optimizaiton("O3");

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 5 ms 640 KB Output is correct
12 Correct 9 ms 768 KB Output is correct
13 Correct 8 ms 768 KB Output is correct
14 Correct 230 ms 768 KB Output is correct
15 Correct 48 ms 768 KB Output is correct
16 Correct 696 ms 888 KB Output is correct
17 Correct 1381 ms 1784 KB Output is correct
18 Correct 1379 ms 1528 KB Output is correct