Submission #732177

#	Time	Username	Problem	Language	Result	Execution time	Memory
732177		Redhood	Pastiri (COI20_pastiri)	C++14	100 / 100	549 ms	83224 KiB

pastiri

#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 (stderr)

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 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51