oj.uz

Submission #732177

# Submission time Handle Problem Language Result Execution time Memory
732177 2023-04-28T14:59:20 Z Redhood Pastiri (COI20_pastiri) C++14
100 / 100
 549 ms 83224 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;

#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define rep(i, n) for (int i = 0; i < (n); ++i)

#ifdef DEBUG

void __dbg(int x) {cout << x;}
void __dbg(bool x) {cout << x;}
void __dbg(ll x) {cout << x;}

void __dbg(auto x) {
    int f = 0;
    for (int i : x)
        cout << (f++ ? ", " : ""), __dbg(i);
}
void _dbg() {
    cout << "]\e[39m" << endl;
}
template<typename T, typename... V>
void _dbg(T t, V... v) {
    __dbg(t);
    if (sizeof...(v))
        cout << ", ";
    _dbg(v...);
}

#define debug(x...) do {cout << "\e[92m" << __func__ << ":" << __LINE__ << "\t[" << #x << "] = ["; _dbg(x); } while (false)
#else
#define debug(...) 42
#endif

void mini(auto &a, auto b) {a = min(a, b); }
void maxi(auto &a, auto b) {a = max(a, b); }

int n, k;
vector<vi> G;
vi dists, tribes, comp;

const int NOT = -1;
const int TOL = -2;

int dfs(int i, int p) {
    bool tolight = (dists[i] == 0);
    bool lightchild = false;

    int bestcomp = -1; // 0 = można tylko tutaj

    for (int j : G[i]) if (j != p) {
        int x = dfs(j, i);
        if (x >= 0 && dists[j] == 1 + dists[i])
            maxi(bestcomp, x);
            
        if (x == TOL) {
            if (dists[j] + 1 == dists[i]) {
                lightchild = true;
            }
            else if (dists[j] == 1 + dists[i]) {
                comp[j] = true;
                maxi(bestcomp, dists[j] - 1);
            }
            else 
                comp[j] = true;
        }
    }

    debug(i, dists[i], bestcomp, tolight, lightchild);

    if (bestcomp >= 0)
        tolight = false;
    if (bestcomp >= 1)
        lightchild = false;

    if (p == -1 && (tolight || lightchild))
        comp[i] = true;

    if (tolight || lightchild)
        return TOL;
    if (bestcomp >= 1)
        return bestcomp - 1;
    return NOT;
}

void solve() {
    cin >> n >> k;
    G.assign(n, vi());
    dists.assign(n, -1);
    comp.assign(n, 0);
    tribes.resize(k);

    rep(_, n-1) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    deque<int> bfs;

    rep(i, k) {
        cin >> tribes[i];
        --tribes[i];
        dists[tribes[i]] = 0;
        bfs.push_back(tribes[i]);
    }

    while (sz(bfs)) {
        int x = bfs[0];
        bfs.pop_front();

        for (int i : G[x]) {
            if (dists[i] != -1)
                continue;
            dists[i] = dists[x] + 1;
            bfs.push_back(i);
        }
    }

    debug(tribes);
    debug(dists);

    dfs(0, -1);

    int cc = accumulate(all(comp), 0);
    cout << cc << '\n';
    rep(i, n) if (comp[i])
        cout << i+1 << ' ';
    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int z = 1;
    // cin >> z;
    while (z--)
        solve();
}

Compilation message

pastiri.cpp:37:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   37 | void mini(auto &a, auto b) {a = min(a, b); }
      |           ^~~~
pastiri.cpp:37:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   37 | void mini(auto &a, auto b) {a = min(a, b); }
      |                    ^~~~
pastiri.cpp:38:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   38 | void maxi(auto &a, auto b) {a = max(a, b); }
      |           ^~~~
pastiri.cpp:38:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   38 | void maxi(auto &a, auto b) {a = max(a, b); }
      |                    ^~~~
pastiri.cpp: In function 'int dfs(int, int)':
pastiri.cpp:34:20: warning: statement has no effect [-Wunused-value]
   34 | #define debug(...) 42
      |                    ^~
pastiri.cpp:71:5: note: in expansion of macro 'debug'
   71 |     debug(i, dists[i], bestcomp, tolight, lightchild);
      |     ^~~~~
pastiri.cpp: In function 'void solve()':
pastiri.cpp:34:20: warning: statement has no effect [-Wunused-value]
   34 | #define debug(...) 42
      |                    ^~
pastiri.cpp:124:5: note: in expansion of macro 'debug'
  124 |     debug(tribes);
      |     ^~~~~
pastiri.cpp:34:20: warning: statement has no effect [-Wunused-value]
   34 | #define debug(...) 42
      |                    ^~
pastiri.cpp:125:5: note: in expansion of macro 'debug'
  125 |     debug(dists);
      |     ^~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 77312 KB Output is correct
2 Correct 196 ms 77352 KB Output is correct
3 Correct 217 ms 77396 KB Output is correct
4 Correct 253 ms 83224 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 428 ms 38900 KB Output is correct
4 Correct 422 ms 41164 KB Output is correct
5 Correct 549 ms 38224 KB Output is correct
6 Correct 518 ms 41804 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 1 ms 432 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 456 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 39456 KB Output is correct
2 Correct 468 ms 39192 KB Output is correct
3 Correct 477 ms 42160 KB Output is correct
4 Correct 510 ms 38284 KB Output is correct
5 Correct 352 ms 34720 KB Output is correct
6 Correct 465 ms 47896 KB Output is correct
7 Correct 453 ms 45372 KB Output is correct
8 Correct 488 ms 44828 KB Output is correct
9 Correct 488 ms 38348 KB Output is correct
10 Correct 513 ms 38472 KB Output is correct
11 Correct 373 ms 40336 KB Output is correct
12 Correct 347 ms 44268 KB Output is correct
13 Correct 383 ms 46120 KB Output is correct
14 Correct 289 ms 42028 KB Output is correct
15 Correct 49 ms 6748 KB Output is correct
16 Correct 492 ms 35536 KB Output is correct
17 Correct 370 ms 35032 KB Output is correct
18 Correct 393 ms 31444 KB Output is correct
19 Correct 476 ms 45284 KB Output is correct
20 Correct 505 ms 49892 KB Output is correct
21 Correct 462 ms 38488 KB Output is correct
22 Correct 465 ms 39184 KB Output is correct