# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
983970 |
2024-05-16T08:39:15 Z |
vjudge1 |
Bosses (BOI16_bosses) |
C++17 |
|
1417 ms |
1400 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define For(i, a, b) for (int i = (a); i <= (b); i++)
#define Ford(i, a, b) for (int i = (b); i >= (a); i --)
#define Rep(i, n) for (int i = 0; i < (n); ++i)
#define Repd(i, n) for (int i = (n) - 1; i >= 0; --i)
#define overload(_1, _2, _3, NAME, ...) NAME
#define FOR(...) overload(__VA_ARGS__, For, Rep)(__VA_ARGS__)
#define FORD(...) overload(__VA_ARGS__, Ford, Repd)(__VA_ARGS__)
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void setupIO(){
#define name "Whisper"
//Phu Trong from Nguyen Tat Thanh High School for gifted student
srand(time(NULL));
cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
//freopen(name".inp", "r", stdin);
//freopen(name".out", "w", stdout);
cout << fixed << setprecision(10);
}
template <class X, class Y>
bool minimize(X &x, const Y &y){
X eps = 1e-9;
if (x > y + eps) {x = y; return 1;}
return 0;
}
template <class X, class Y>
bool maximize(X &x, const Y &y){
X eps = 1e-9;
if (x + eps < y) {x = y; return 1;}
return 0;
}
const int MAX = 1e4 + 5;
struct Edge{
int u, v, w;
Edge(){}
Edge(int _u, int _v): u(_u), v(_v){}
Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w){}
int other(int x){return (x ^ u ^ v); }
} edge[MAX];
vector<int> G[MAX];
int numNode;
int bfs(int root){
queue<pair<int, int>> q;
vector<int> vis(numNode + 1);
q.emplace(root, 1);
vis[root] = 1;
while (q.size()){
int u = q.front().first;
int st = q.front().second;
q.pop();
for (int &i : G[u]){
int v = edge[i].other(u);
if(vis[v]) continue;
vis[v] = st + 1;
q.emplace(v, st + 1);
}
}
sort(vis.begin() + 1, vis.end(), greater<int>());
int ans = 0;
for (int i = 1; i <= numNode; ++i){
if(!vis[i]) return LINF;
ans += vis[i];
}
return ans;
}
void Whisper(){
cin >> numNode;
int cnt = 0;
for (int i = 1; i <= numNode; ++i){
int numEdge; cin >> numEdge;
for (int v = 1; v <= numEdge; ++v){
++cnt;
edge[cnt].u = i;
cin >> edge[cnt].v;
G[edge[cnt].v].emplace_back(cnt);
}
}
int ans = LINF;
for (int i = 1; i <= numNode; ++i){
minimize(ans, bfs(i));
}
cout << ans;
}
signed main(){
setupIO();
int Test = 1;
// cin >> Test;
for ( int i = 1 ; i <= Test ; i++ ){
Whisper();
if (i < Test) cout << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
604 KB |
Output is correct |
7 |
Correct |
0 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
0 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
604 KB |
Output is correct |
2 |
Correct |
0 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
0 ms |
604 KB |
Output is correct |
7 |
Correct |
0 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
0 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
6 ms |
860 KB |
Output is correct |
13 |
Correct |
5 ms |
860 KB |
Output is correct |
14 |
Correct |
621 ms |
860 KB |
Output is correct |
15 |
Correct |
235 ms |
1212 KB |
Output is correct |
16 |
Correct |
1031 ms |
1400 KB |
Output is correct |
17 |
Correct |
1417 ms |
1116 KB |
Output is correct |
18 |
Correct |
1365 ms |
1124 KB |
Output is correct |