Submission #1097588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097588		BLOBVISGOD	Railway (BOI17_railway)	C++17	36 / 100	108 ms	27024 KiB

railway

#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int n,m,k; cin >> n >> m >> k;

    map<pair<int,int>,int> to_input;
    vvi adj(n);
    rep(i,0,n-1){
        int u,v; cin >> u >> v;
        u--,v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
        if (u>v) swap(u,v);
        to_input[{u,v}] = i;
    }   

    int cc = 0;
    vi d(n), vis(n), dfsord(n);
    vvi par(__lg(n)+1,vi(n));
    auto dfs = [&](int at, int dep, auto&& self) -> void {
        vis[at] = 1;
        d[at] = dep;
        for(auto to : adj[at]) if (!vis[to]){
            par[0][to] = at;
            self(to,dep+1,self);
        }
        dfsord[at] = cc++;
    };
    dfs(0,0,dfs);
    rep(i,0,__lg(n)) rep(j,0,n) par[i+1][j] = par[i][par[i][j]];
    auto jmp = [&](int at, int k) -> int {
        for(int i = 0; k; i++,k/=2) if (k&1) at = par[i][at];
        return at;
    };

    auto lca = [&](int u, int v) -> int {
        if (d[u] < d[v]) swap(u,v);
        u = jmp(u,d[u]-d[v]);
        if (u==v) return u;
        for(int i = __lg(n); i>=0; --i) 
            if (par[i][u] != par[i][v])
                u = par[i][u], v = par[i][v];
        return par[0][u];
    };

    vi cnt(n);
    auto addpath = [&](int at, int rt) -> void {
        if (d[at] <= d[rt]) return;
        cnt[at]++;
        cnt[rt]--;
    };

    rep(i,0,m){
        int t; cin >> t;
        vi a(t);
        rep(i,0,t) cin >> a[i], a[i]--;
        if (t<2) continue;
        sort(all(a),[&](int u, int v){
            return dfsord[u] < dfsord[v];
        });

        rep(l,0,t){
            int r = (l+1)%t;
            int lc = lca(a[l],a[r]);
            addpath(a[l],lc);
            addpath(a[r],lc);
        }
    }

    fill(all(vis),0);
    auto prop = [&](int at, auto&& self) -> void {
        vis[at] = 1;
        for(auto to : adj[at]) if (!vis[to]){
            self(to,self);
            cnt[at] += cnt[to];
        }
    };

    prop(0, prop);

    vi ans;

    rep(i,0,n) if (cnt[i] >= k*2) ans.push_back(i);
    cout << sz(ans) << '\n';
    for(auto c : ans) {
        int ot = par[0][c];
        if (c > ot) swap(c,ot);
        assert(to_input.count({c,ot}));
        cout << to_input[{c,ot}]+1 << ' ';
    }
    cout << '\n';
}

/*

9 1 1
1 2 
1 3
2 4
2 5
2 6
3 7
6 8
6 9
6 3 2 5 6 8 9

*/

/*

9 1 1
1 2 
1 3
2 4
2 5
2 6
3 7
6 8
6 9
5 7 2 5 6 8 

*/


/*

13 2 2
1 2 
1 3
2 4
2 5
2 6
3 7
6 8
6 9
7 10
1 11
11 12
12 13
9 10 3 8 9 4 13 12 11 1
5 7 2 5 6 8 

*/

/*

10 2 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
5 1 3 5 7 9
5 2 4 6 8 10


*/

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