Submission #171283

#	Time	Username	Problem	Language	Result	Execution time	Memory
171283		AM1648	Railway (BOI17_railway)	C++17	100 / 100	503 ms	33784 KiB

railway

/* be name khoda */

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

#define forifrom(i, s, n) for (ll i = (s); i < (n); ++i)
#define fori(i, n) forifrom(i, 0, n)
#define forirto(i, n, e) for (ll i = (n) - 1; i >= (e); --i)
#define forir(i, n) forirto(i, n, 0)

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define F first
#define S second

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpii;

const ll maxn = 100010;
const ll maxnlg = 20;

ll n, m, k;
vpii g[maxn];
ll st[maxn], ft[maxn], pars[maxnlg][maxn];
vi vers;
ll ps[maxn];
ll es[maxn];

ll tim = 0;
void dfs_stft(ll x, ll par) {
    st[x] = tim++;
    pars[0][x] = par;
    fori (i, maxnlg - 1) {
        pars[i + 1][x] = pars[i][pars[i][x]];
    }
    for (auto y : g[x]) {
        if (y.F != par) {
            dfs_stft(y.F, x);
        }
    }
    ft[x] = tim;
}

ll LCA(ll a, ll b) {
    if (st[a] > st[b]) swap(a, b);
    if (ft[a] >= ft[b]) return a;
    forir (i, maxnlg) {
        if (ft[pars[i][a]] < ft[b]) a = pars[i][a];
    }
    return pars[0][a];
}

void add_path(ll a, ll b, ll d) {
    ps[a] += d;
    ps[b] += d;
    ps[LCA(a, b)] -= 2 * d;
}

bool st_cmp(ll a, ll b) {
    return st[a] < st[b];
}

void dfs_sum(ll x, ll par) {
    for (auto y : g[x]) {
        if (y.F != par) {
            dfs_sum(y.F, x);
            ps[x] += ps[y.F];
            es[y.S] += ps[y.F];
        }
    }
}

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

    cin >> n >> m >> k;
    fori (i, n - 1) {
        ll a, b; cin >> a >> b;;
        g[a].pb({b, i}), g[b].pb({a, i});
    }

    g[0].pb({1, n});
    dfs_stft(0, 0);

    fori (i, m) {
        ll c; cin >> c;
        vers.clear();
        fori (j, c) {
            ll x; cin >> x;
            vers.pb(x);
        }
        if (c == 1) continue;
        sort(all(vers), st_cmp);
        add_path(vers[0], vers.back(), 2);
        forifrom (i, 1, vers.size() - 1) {
            add_path(vers[i - 1], vers[i], 1);
            add_path(vers.back(), vers[i], 1);
            add_path(vers[i - 1], vers.back(), -1);
        }
    }

    dfs_sum(0, 0);

    ll ans = 0;
    fori (i, n - 1) {
        if (es[i] >= k * 2) ++ans;
    }
    cout << ans << '\n';
    fori (i, n - 1) {
        if (es[i] >= k * 2) cout << i + 1 << ' ';
    }
    cout << '\n';

}

/*
6 3 2
1 3
2 3
3 4
6 4
4 5
4 1 3 2 5
2 6 3
2 3 2
*/

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:9:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forifrom(i, s, n) for (ll i = (s); i < (n); ++i)
                                              ^
railway.cpp:100:9: note: in expansion of macro 'forifrom'
         forifrom (i, 1, vers.size() - 1) {
         ^~~~~~~~

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