oj.uz

Submission #785494

# Submission time Handle Problem Language Result Execution time Memory
785494 2023-07-17T09:38:35 Z RecursiveCo Bosses (BOI16_bosses) C++14
100 / 100
 732 ms 764 KB 
// CF template, version 3.0

#include <bits/stdc++.h>

using namespace std;

#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}

#define int long long

vector<vector<int>> adjList;

int solve(int v) {
    // What is the minimum possible sum of salaries (n + sum of heights) if we root the tree at v?
    int n = adjList.size();
    int ans = n;
    vector<bool> visited(n, false);
    vector<int> dist(n, 1e18);
    queue<pair<int, int>> bfs;
    bfs.push({0, v});
    while (!bfs.empty()) {
        auto top = bfs.front();
        int distance = top.first;
        int node = top.second;
        bfs.pop();
        if (visited[node]) continue;
        dist[node] = min(dist[node], distance);
        visited[node] = true;
        for (int con: adjList[node]) {
            if (!visited[con]) bfs.push({dist[node] + 1, con});
        }
    }
    forto(n, i) if (!visited[i]) return 1e18;
    forto(n, i) ans += dist[i];
    return ans;
}

signed main() {
    improvePerformance;
    //getTest;

    //eachTest {
        get(n);
        adjList.resize(n);
        forto(n, i) {
            get(cnt);
            forto(cnt, j) {
                get(v);
                v--;
                adjList[v].push_back(i);
            }
        }
        int ans = 1e18;
        forto(n, i) {
            ans = min(ans, solve(i));
        }
        out(ans);
    //}
}

Compilation message

bosses.cpp: In function 'long long int solve(long long int)':
bosses.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
bosses.cpp:42:5: note: in expansion of macro 'forto'
   42 |     forto(n, i) if (!visited[i]) return 1e18;
      |     ^~~~~
bosses.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
bosses.cpp:43:5: note: in expansion of macro 'forto'
   43 |     forto(n, i) ans += dist[i];
      |     ^~~~~
bosses.cpp: In function 'int main()':
bosses.cpp:10:23: warning: unnecessary parentheses in declaration of 'n' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
bosses.cpp:52:9: note: in expansion of macro 'get'
   52 |         get(n);
      |         ^~~
bosses.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
bosses.cpp:54:9: note: in expansion of macro 'forto'
   54 |         forto(n, i) {
      |         ^~~~~
bosses.cpp:10:23: warning: unnecessary parentheses in declaration of 'cnt' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
bosses.cpp:55:13: note: in expansion of macro 'get'
   55 |             get(cnt);
      |             ^~~
bosses.cpp:15:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
bosses.cpp:56:13: note: in expansion of macro 'forto'
   56 |             forto(cnt, j) {
      |             ^~~~~
bosses.cpp:10:23: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
bosses.cpp:57:17: note: in expansion of macro 'get'
   57 |                 get(v);
      |                 ^~~
bosses.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
bosses.cpp:63:9: note: in expansion of macro 'forto'
   63 |         forto(n, i) {
      |         ^~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 324 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 15 ms 564 KB Output is correct
13 Correct 15 ms 584 KB Output is correct
14 Correct 137 ms 596 KB Output is correct
15 Correct 13 ms 628 KB Output is correct
16 Correct 517 ms 764 KB Output is correct
17 Correct 732 ms 688 KB Output is correct
18 Correct 704 ms 688 KB Output is correct