Submission #1052637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052637		turska	Railway (BOI17_railway)	C++17	100 / 100	120 ms	31124 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define P push_back
#define N 100001
#define I int
#define S size()
#define V vector
#define M map<I, I>
I n, m, k, u, v, s, h, z[N];
V<pair<I, I>> X[N];
V<I> A, q[N];
M G(I v, I p) {
    M a;
    for (auto [u, i]: X[v]) if (u^p) {
        M b = G(u, v);
        if (b.S>=k)  A.P(i);
        if (a.S < b.S) a.swap(b);
        for (auto [k, v]: b) 
            if (a[k]+v==z[k]) a.erase(k);
            else a[k] += v;
    }
    for (auto u: q[v]) {
        a[u]++;
        if (a[u] == z[u]) a.erase(u);
    }
    return a;
}
I main() {
    cin>>n>>m >>k;
    for (I i=0; i<n-1; i++) {
        cin >> u >> v;
        X[u].P({v, i});
        X[v].P({u, i});
    }
    for (I i=0; i<m; i++) {
        cin >> s;
        z[i] = s;
        for (I j=0; j<s; j++) {
            cin >> h;
            q[h].P(i);
        }
    }
    G(1, 1);
    sort(A.begin(), A.end());
    cout << A.S << '\n';
    for (auto i: A) cout << i+1 << ' ';
}

Compilation message (stderr)

railway.cpp: In function 'std::map<int, int> G(int, int)':
railway.cpp:16:16: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |         if (b.S>=k)  A.P(i);
      |             ~~~^~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25