Submission #754200

#	Time	Username	Problem	Language	Result	Execution time	Memory
754200		hafo	Railway (BOI17_railway)	C++14	100 / 100	134 ms	26832 KiB

railway

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 7;
const ll oo = 1e18 + 69;

int n, m, k, u, v, id[maxn], timer = 0, st[maxn], en[maxn], ex[maxn], res[maxn], edge_id[maxn];
vector<pa> g[maxn];

struct LCA {
    int p[LOG][maxn], f[maxn];

    void dfs(int u, int par) {
        id[u] = ++timer;
        p[0][u] = par;
        for(auto e:g[u]) {
            int v = e.fi;
            if(v == par) continue;
            f[v] = f[u] + 1;
            dfs(v, u);
        }
    }

    int get_lca(int u, int v) {
        if(f[u] < f[v]) swap(u, v);
        int k = f[u] - f[v];
        for(int i = 0; i < LOG; i++)
            if((k >> i) & 1) u = p[i][u];
        if(u == v) return u;
        for(int i = LOG - 1; i >= 0; i--)
        if(p[i][u] != p[i][v]) {
            u = p[i][u];
            v = p[i][v];
        }
        return p[0][u];
    }

    void init() {
        f[1] = 0;
        dfs(1, 0);
        for(int i = 1; i < LOG; i++) {
            for(int u = 1; u <= n; u++) p[i][u] = p[i - 1][p[i - 1][u]];
        }
    }

    int jump(int u, int k) {
        for(int i = 0; i < LOG; i++)
            if((k >> i) & 1) u = p[i][u];
        return u;
    }

    void add(int u, int v) {
        int par = get_lca(u, v);
        st[u]++;
        st[v]++;
        en[par] += 2;
        if(u != par && v != par) ex[par]++;
        else {
            st[par]--;
            en[par]--;
        }
    }

    void update(int u, int v) {
        int par = get_lca(u, v);
        if(u != par) add(u, jump(u, f[u] - f[par] - 1));
        if(v != par) add(v, jump(v, f[v] - f[par] - 1));
    }

} lca;

bool cmp(int a, int b) {
    return id[a] < id[b];
}

void dfs(int u, int par) {
    for(auto e:g[u]) {
        int v = e.fi;
        if(v == par) continue;
        edge_id[v] = e.se;
        dfs(v, u);
        st[u] += st[v];
    }
    res[u] = st[u] - ex[u];
    st[u] -= en[u];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    cin>>n>>m>>k;
    for(int i = 1; i < n; i++) {
        cin>>u>>v;
        g[u].pb({v, i});
        g[v].pb({u, i});
    }

    lca.init();
    while(m--) {
        cin>>u;
        vector<int> a;
        for(int i = 0; i < u; i++) {
            cin>>v;
            a.pb(v);
        }
        sort(all(a), cmp);
        for(int i = 0; i < u; i++) {
            int j = (i + 1) % u;
            lca.update(a[i], a[j]);
        }
    }

    dfs(1, 0);
    vector<int> ans;
    for(int i = 1; i <= n; i++) {
        if(res[i] >= 2 * k) ans.pb(edge_id[i]);
    }
    cout<<Size(ans)<<"\n";
    sort(all(ans));
    for(auto i:ans) cout<<i<<" ";
    return 0;
}

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