oj.uz

Submission #949946

# Submission time Handle Problem Language Result Execution time Memory
949946 2024-03-20T00:20:00 Z vjudge306 Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 1316 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, v2; v1.push(root); int v[n+2]={}; vector<int>adj[n+2]; --n; v[root]=1;

while ((!v1.empty()||!v2.empty())) {
        if (!n)break;
    if (!v1.empty()) {
       while (!v1.empty()) {
        int x=v1.front(); v1.pop();
        for (auto i:ch[x])
            if (!v[i]) adj[x].emp(i), v[i]=1, v2.push(i),n--;
       }
    }
    else {
        while (!v2.empty()) {
        int x=v2.front(); v2.pop();
        for (auto i:ch[x])
            if (!v[i]) adj[x].emp(i), v[i]=1, v1.push(i),n--;
       }
    }
}
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:51:11: warning: unused variable 'x' [-Wunused-variable]
   51 |  sm=0; ll x=dfs(root, root, adj);
      |           ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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 460 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 600 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 460 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 3 ms 348 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 321 ms 856 KB Output is correct
15 Correct 58 ms 836 KB Output is correct
16 Correct 954 ms 980 KB Output is correct
17 Execution timed out 1507 ms 1316 KB Time limit exceeded
18 Halted 0 ms 0 KB -