oj.uz

Submission #950188

# Submission time Handle Problem Language Result Execution time Memory
950188 2024-03-20T06:40:07 Z vjudge306 Bosses (BOI16_bosses) C++14
100 / 100
 844 ms 1076 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define nn "\n"
#define x_x ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define intt int _; cin >> _; while (_--)
#define emp push_back
#define mod 1000000007
#define all(v) v.begin(), v.end()
#define ld long double
#define A first
#define B second
//#define int long long
typedef long long ll;
const ld eps = 1e-27;
// diff between decimals 0.000000001 mt19937 mt(time(nullptr));
ll sm=0;
ll dfs(int i, int p, vector<int>adj[]) {
ll x=0;
for (auto j:adj[i]) {
    if (p!=j) x+=dfs(j,i,adj);
}
sm+=x+1;
return x+1;
}
 int v[5002]={}; vector<int>adj[5002];
ll fun(int root, int n, vector<int>ch[]) {
queue<int>v1; v1.push(root); for (int i=1; i<=n; i++)v[i]=0, adj[i].clear();
v[root]=1; n--;
while (!v1.empty()) {
    int x=v1.front(); v1.pop();
    for (auto i:ch[x])
        if (!v[i])n--,v[i]=1, v1.push(i), adj[x].emp(i);
}
if (n) return LLONG_MAX;
 sm=0; ll x=dfs(root, root, adj);
return sm;
}
int main() {

    x_x
    int n; cin>>n; vector<int>ch[n+2];
    for (int i=1,k,c; i<=n; i++) {
        cin>>k; while(k--) cin>>c, ch[c].emp(i);
    }
    ll ans=LLONG_MAX;
    for (int i=1; i<=n; i++)
        ans=min(ans, fun(i,n,ch));

    cout<<ans;
  return 0;
}

Compilation message

bosses.cpp: In function 'll fun(int, int, std::vector<int>*)':
bosses.cpp:39:11: warning: unused variable 'x' [-Wunused-variable]
   39 |  sm=0; ll x=dfs(root, root, adj);
      |           ^

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 576 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 356 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 600 KB Output is correct
14 Correct 128 ms 1028 KB Output is correct
15 Correct 19 ms 860 KB Output is correct
16 Correct 525 ms 860 KB Output is correct
17 Correct 804 ms 1072 KB Output is correct
18 Correct 844 ms 1076 KB Output is correct