Submission #1113521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113521		ShaShi	Railway (BOI17_railway)	C++17	100 / 100	237 ms	78960 KiB

railway

#include <bits/stdc++.h>
 
#define int long long  

// #pragma GCC  ("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
 
#define F first 
#define S second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << "\n", exit(0);
#define pii pair<int, int>
#define pll pair<long long, long long>
#define endl "\n"
 
 
 
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef long double ld;
 
 
const int MAXN = (int)1e6 + 7;
const ll MOD = (int)1e9 + 7;
const int INF = (int)1e9 + 7;
const int LG = 20;


int n, m, k, t, tmp, tmp2, tmp3, tmp4, u, v, w, flag, q, ans;
int arr[MAXN], st[MAXN], ft[MAXN], blk[MAXN], sz[MAXN], h[MAXN], par[MAXN];
int pow2dad[MAXN][LG], edge_id[MAXN], res[MAXN], ind[MAXN];
vector<int> adj[MAXN], final_res;
vector<pii> edge, vec;



/* Segment Tree */
#define mid ((l+r)>>1)
#define lid (id<<1)
#define rid (lid|1)


int seg[MAXN<<2], lazy[MAXN<<2];


inline void relax(int l, int r, int id) {
    if (lazy[id] == 0) return;

    seg[lid] += lazy[id]*(mid-l); lazy[lid] += lazy[id];
    seg[rid] += lazy[id]*(r-mid); lazy[rid] += lazy[id];

    lazy[id] = 0;
}


void upd(int s, int t, int l=0, int r=n, int id=1) {
    if (s >= t) return;

    if (s <= l && t >= r) {
        seg[id] += r-l; lazy[id]++;
        return;
    }
    
    relax(l, r, id);

    if (s < mid) upd(s, t, l, mid, lid);
    if (t > mid) upd(s, t, mid, r, rid);

    seg[id] = seg[lid]+seg[rid];
}


void rebuild(int l=0, int r=n, int id=1) {
    if (l+1 == r) {
        res[ind[l]] = seg[id];
        return;
    }

    relax(l, r, id);

    rebuild(l, mid, lid);
    rebuild(mid, r, rid);
}

/* Segment Tree */


/* LCA */

inline int up(int v, int k) {
    for (int i=LG-1; i>=0; i--) {
        if (k >= (1<<i)) {
            v = pow2dad[v][i];
            k -= (1<<i);
        }
    }

    return v;
}


inline int LCA(int u, int v) {
    if (h[u] < h[v]) swap(u, v);

    u = up(u, h[u]-h[v]);

    for (int i=LG-1; i>=0; i--) {
        if (h[u] >= (1<<i) && pow2dad[u][i] != pow2dad[v][i]) {
            u = pow2dad[u][i];
            v = pow2dad[v][i];
        }
    }

    if (u == v) return u;
    return par[v];
}

/* LCA */


/* HLD */

void DFSsz(int v) {
    sz[v] = 1;

    for (int u:adj[v]) {
        if (u == par[v]) continue;

        par[u] = v; h[u] = h[v]+1;

        DFSsz(u);

        sz[v] += sz[u];
    }
}


void DFS(int v, int head) {
    st[v] = flag; ind[flag++] = v; blk[v] = head;

    int big = 0;
    for (int u:adj[v]) if (u != par[v] && sz[u] > sz[big]) big = u;

    if (big) DFS(big, head);

    for (int u:adj[v]) if (u != par[v] && u != big) DFS(u, u);

    ft[v] = flag;
}


void inc_direct_path(int u, int v) {
    if (blk[u] != blk[v]) {
        upd(st[blk[u]], st[u]+1);
        inc_direct_path(par[blk[u]], v);
    } else {
        upd(st[v]+1, st[u]+1);
    }
}


inline void inc_path(int u, int v) {
    if (h[u] < h[v]) swap(u, v);

    int lca = LCA(u, v);
    
    if (lca == v) inc_direct_path(u, v);
    else inc_direct_path(u, lca), inc_direct_path(v, lca);
}

/* HLD */




int32_t main() {
    #ifdef LOCAL
    freopen("inp.in", "r", stdin);
    freopen("res.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    
    cin >> n >> q >> k;

    for (int i=1; i<n; i++) {
        cin >> u >> v;

        edge.pb({u, v}); adj[u].pb(v); adj[v].pb(u);
    }

    DFSsz(1);

    for (int i=0; i<n-1; i++) {
        u = edge[i].F; v = edge[i].S;

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

        edge_id[u] = i+1;
    }

    DFS(1, 1);

    for (int i=1; i<=n; i++) pow2dad[i][0] = par[i];
    for (int j=1; j<LG; j++) for (int i=1; i<=n; i++) pow2dad[i][j] = pow2dad[pow2dad[i][j-1]][j-1];


    for (int i=1; i<=q; i++) {
        cin >> m; vec.clear();

        for (int j=1; j<=m; j++) {
            cin >> u;

            vec.pb({st[u], u});
        }

        sort(all(vec));

        for (int j=0; j<m-1; j++) inc_path(vec[j].S, vec[j+1].S);
        inc_path(vec[0].S, vec[m-1].S);
    }

    rebuild();

    for (int i=1; i<=n; i++) if (res[i] >= 2*k) final_res.pb(edge_id[i]);

    sort(all(final_res));

    cout << final_res.size() << endl;

    for (auto cur:final_res) cout << cur << " ";
    cout << endl;


    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