oj.uz

Submission #732160

# Submission time Handle Problem Language Result Execution time Memory
732160 2023-04-28T14:28:52 Z Redhood Pastiri (COI20_pastiri) C++14
8 / 100
 496 ms 85392 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(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, dfsret;

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

int dfs(int i, int p) {
    bool tolight = (dists[i] == 0);
    int bestcomp = -1; // 0 = można tylko tutaj

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

    debug(i, bestcomp);

    if (bestcomp >= 0)
        tolight = false;

    if (i == 0 && tolight)
        comp[i] = true;

    if (tolight)
        return dfsret[i] = TOL;
    if (bestcomp > 0)
        return dfsret[i] = bestcomp - 1;
    return dfsret[i] = NOT;
}

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

    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:36:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   36 | void mini(auto &a, auto b) {a = min(a, b); }
      |           ^~~~
pastiri.cpp:36:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   36 | void mini(auto &a, auto b) {a = min(a, b); }
      |                    ^~~~
pastiri.cpp:37:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   37 | void maxi(auto &a, auto b) {a = max(a, b); }
      |           ^~~~
pastiri.cpp:37:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   37 | void maxi(auto &a, auto b) {a = max(a, b); }
      |                    ^~~~
pastiri.cpp: In function 'int dfs(int, int)':
pastiri.cpp:33:20: warning: statement has no effect [-Wunused-value]
   33 | #define debug(...) 42
      |                    ^~
pastiri.cpp:68:5: note: in expansion of macro 'debug'
   68 |     debug(i, bestcomp);
      |     ^~~~~
pastiri.cpp: In function 'void solve()':
pastiri.cpp:33:20: warning: statement has no effect [-Wunused-value]
   33 | #define debug(...) 42
      |                    ^~
pastiri.cpp:120:5: note: in expansion of macro 'debug'
  120 |     debug(tribes);
      |     ^~~~~
pastiri.cpp:33:20: warning: statement has no effect [-Wunused-value]
   33 | #define debug(...) 42
      |                    ^~
pastiri.cpp:121:5: note: in expansion of macro 'debug'
  121 |     debug(dists);
      |     ^~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 79296 KB Output is correct
2 Correct 204 ms 79308 KB Output is correct
3 Correct 200 ms 79376 KB Output is correct
4 Correct 253 ms 85392 KB Output is correct

Subtask #2
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 Incorrect 411 ms 40780 KB Sheep 147092 not protected
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Sheep 208 not protected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 496 ms 41412 KB Sheep 680 not protected
2 Halted 0 ms 0 KB -