Submission #1268370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268370		QuocSensei	Railway (BOI17_railway)	C++17	45 / 100	102 ms	28604 KiB

railway

#include <bits/stdc++.h>

// #define int long long

#define TASK "test"
#define ll long long
#define fi first
#define sc second
#define ii pair <int, int>  
#define iii pair <int, ii>

using namespace std;

const int MAXN = 1e5;
const int INF = 2e9;
const ll LINF = 1e18;
const int LOG = 16;

int n, m, k, cnt = 0;
int tin[MAXN + 5], h[MAXN + 5], p[MAXN + 5][LOG + 5], dp[MAXN + 5], mark[MAXN + 5];
vector <ii> adj[MAXN + 5];
vector <int> new_adj[MAXN + 5];
vector <int> vec, new_vec;

void Dfs(int u, int par) {
    tin[u] = ++cnt;
    for (auto v : adj[u]) {
        if (v.fi == par) continue;
        h[v.fi] = h[u] + 1;
        p[v.fi][0] = u;
        Dfs(v.fi, u);
    }
}

void lastDfs(int u, int par) {
    for (auto v : adj[u]) {
        if (v.fi == par) continue;
        lastDfs(v.fi, u);
        dp[u] += dp[v.fi];
        mark[v.sc] += dp[v.fi];
    }
}

void Build_LCA() {
    for (int j = 1; j <= LOG; j++)
        for (int i = 1; i <= n; i++)
            p[i][j] = p[p[i][j - 1]][j - 1];

    h[0] = -1;
}

int lca(int u, int v) {
    if (h[u] < h[v]) return lca(v, u);

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

    if (u == v) return u;

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

    return p[u][0];
}

bool cmp(int u, int v) {
    return tin[u] <= tin[v];
}

void build_virtual_tree() {
    vector <int> stk;
    for (int i = 0; i < (int)new_vec.size(); i++) {
        while (!stk.empty() and lca(stk.back(), new_vec[i]) != stk.back()) stk.pop_back();
        if (!stk.empty()) {
            new_adj[new_vec[i]].push_back(stk.back());
            new_adj[stk.back()].push_back(new_vec[i]);
        }

        stk.push_back(new_vec[i]);
    }
}

signed main() {
    // #ifndef ONLINE_JUDGE
    // freopen(TASK".inp", "r", stdin);
    // freopen(TASK".out", "w", stdout);
    // #endif
    cin.tie(0)->sync_with_stdio(false);
    
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    Dfs(1, -1);
    Build_LCA();

    for (int i = 1; i <= m; i++) {
        vec.clear();
        new_vec.clear();
        int x; cin >> x;
        for (int j = 1; j <= x; j++) {
            int u; cin >> u;
            vec.push_back(u);
        }

        sort(vec.begin(), vec.end(), cmp);
        
        new_vec = vec;

        for (int j = 0; j < (int)vec.size() - 1; j++)
            new_vec.push_back(lca(vec[j], vec[j + 1]));

        sort(new_vec.begin(), new_vec.end(), cmp);

        new_vec.resize(unique(new_vec.begin(), new_vec.end()) - new_vec.begin());

        build_virtual_tree();

        int mi = cnt + 1, root;

        for (auto u : new_vec) {
            if (tin[u] < mi) {
                mi = tin[u];
                root = u;
            } 
        }

        // cout << new_adj[4].size() << endl;


        for (auto u : new_vec) {
            // if (i == 2) cout << u << ' ' << new_adj[u].size() << endl;
            if (u != root) 
                dp[u] += 1 - ((int)new_adj[u].size() - 1);
            else 
                dp[u] += - (int)new_adj[u].size() - 1;

            new_adj[u].clear();
        }

        // if (i == 2) break;
    }

    lastDfs(1, -1);

    // for (int i = 1; i <= n; i++) cout << dp[i] << endl;

    vector <int> ans;

    for (int i = 1; i < n; i++) {
        // cout << mark[i] << endl;
        if (mark[i] >= k) 
            ans.push_back(i);
    }

    cout << (int)ans.size() << '\n';

    sort(ans.begin(), ans.end());

    for (auto u : ans) cout << u << ' ';

    return 0;
}

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