# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
243687 |
2020-07-01T14:37:19 Z |
kimbj0709 |
Bosses (BOI16_bosses) |
C++14 |
|
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");
# |
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 |
# |
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 |
# |
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 |