oj.uz

Submission #949947

# Submission time Handle Problem Language Result Execution time Memory
949947 2024-03-20T00:24:34 Z vjudge306 Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 1104 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;
}

ll fun(int root, int n, vector<int>ch[]) {
queue<int>v1; v1.push(root); int v[n+2]={}; vector<int>adj[n+2]; --n; v[root]=1;
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:38:11: warning: unused variable 'x' [-Wunused-variable]
   38 |  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 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 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 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 496 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #3
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 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 496 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 4 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 318 ms 1004 KB Output is correct
15 Correct 45 ms 848 KB Output is correct
16 Correct 955 ms 1104 KB Output is correct
17 Execution timed out 1548 ms 1008 KB Time limit exceeded
18 Halted 0 ms 0 KB -