Submission #502225

#	Time	Username	Problem	Language	Result	Execution time	Memory
502225		Lobo	Railway (BOI17_railway)	C++17	100 / 100	150 ms	29432 KiB

railway

#include<bits/stdc++.h>
using namespace std;

/*for ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
*/

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 110000

ii n, m, k, cnt[maxn], p[maxn][25], ps[maxn], h[maxn];
vector<pair<ii,ii>> edg, g[maxn];
ii tin[maxn], timer = 1;

ii lca(ii u, ii v) {
    if(h[u] < h[v]) swap(u,v);

    for(ii i = 20; i >= 0; i--) {
        if(h[p[u][i]] >= h[v]) {
            u = p[u][i];
        }
    }

    if(u == v) {
        return u;
    }

    for(ii i = 20; i >= 0; i--) {
        if(p[u][i] != p[v][i]) {
            u = p[u][i];
            v = p[v][i];
        }
    }

    return p[u][0];
}


void dfslca(ii u, ii ant, ii id) {
    //.fr = pai .sc = filho
    if(u != 1 && edg[id].fr == u) swap(edg[id].fr,edg[id].sc);
    tin[u] = timer++;

    p[u][0] = ant;
    for(ii i = 1; i <= 20; i++) {
        p[u][i] = p[p[u][i-1]][i-1];
    }

    for(auto V : g[u]) {
        ii v = V.fr;
        ii id1 = V.sc;
        if(v == ant) continue;
        h[v] = h[u]+1;
        
        dfslca(v,u,id1);
    }
}

void dfsps(ii u, ii ant) {
    for(auto V : g[u]) {
        ii v = V.fr;
        if(v == ant) continue;
        
        dfsps(v,u);
        ps[u]+= ps[v];
    }
}

void solve() {
    cin >> n >> m >> k;

    for(ii i = 0; i < n-1; i++) {
        ii a, b;
        cin >> a >> b;

        g[a].pb(mp(b,i));
        g[b].pb(mp(a,i));
        edg.pb(mp(a,b));
    }

    h[1] = 0;
    dfslca(1,1,0);

    while(m--) {
        ii s; cin >> s;
        vector<pair<ii,ii>> vert;
        for(ii i = 0; i < s; i++) {
            ii u; cin >> u;
            vert.pb(mp(tin[u],u));
        }

        sort(all(vert));

        for(ii i = 0; i < s; i++) {
            ii u = vert[i].sc;
            ii v = vert[(i+1)%s].sc;
            ii lc = lca(u,v);

            ps[u]++;
            ps[v]++;
            ps[lc]-= 2;
        }

          
    }

    dfsps(1,1);
    for(ii i = 0; i < n-1; i++) {
        ii v = edg[i].sc;
        cnt[i] = ps[v]/2;
    }

    

    vector<ii> ans;
    for(ii i = 0; i < n-1; i++) {
        if(cnt[i] >= k) ans.pb(i+1);
    }

    cout << ans.size() << endl;
    for(auto x : ans) cout << x << " ";
    cout << endl;

}

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

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    ii tt = 1;
    // cin >> tt;
    while(tt--) solve();

}

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