Submission #1280049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280049		swishy123	Railway (BOI17_railway)	C++20	0 / 100	1096 ms	29892 KiB

railway

#include <bits/stdc++.h>

using namespace std;

const int def = 1e5+1;
const int k = 18;

int f[def][k];
void solve(){
    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<int>> edg(n);
    map<pair<int, int>, int> mp;

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

        u--; v--;
        edg[u].push_back(v);
        edg[v].push_back(u);

        mp[{u, v}] = mp[{v, u}] = i + 1;
    }

    for (int i = 0; i < n; i++) for (int j = 0; j < k; j++)
        f[i][j] = -1;

    vector<int> order(n, 0), h(n, 0);
    int t = 0;

    auto dfs = [&](int u, int pre, auto&& dfs) -> void{
        order[u] = t++;
        for (int v : edg[u]){
            if (v == pre)
                continue;
            f[v][0] = u;
            h[v] = h[u] + 1;
            dfs(v, u, dfs);
        }
    };
    dfs(0, -1, dfs);

    for (int j = 1; j < k; j++) for (int i = 0; i < n; i++){
        int p = f[i][j - 1];
        if (p != -1)
            f[i][j] = f[p][j - 1];
    }

    auto lca = [&](int u, int v) -> int{
        if (h[u] < h[v])
            swap(u, v);
        for (int j = k - 1; j >= 0; j--){
            if (f[u][j] != -1 && h[f[u][j]] >= h[v])
                u = f[u][j];
        }
        if (u == v)
            return u;
        for (int j = k - 1; j >= 0; j--){
            if (f[u][j] != -1 && f[v][j] != -1 && f[u][j] != f[v][j]){
                u = f[u][j];
                v = f[v][j];
            }
        }
        return f[u][0];
    };      

    vector<int> add(n, 0);
    for (int i = 0; i < m; i++){
        int s;
        cin >> s;

        vector<int> node;
        for (int j = 0; j < s; j++){
            int u; cin >> u;
            node.push_back(u - 1);
        }
        sort(node.begin(), node.end(), [&](int a, int b){ return order[a] < order[b]; });
        int m = node.size();

        for (int j = 0; j < m - 1; j++)
            node.push_back(lca(node[j], node[j + 1]));

        sort(node.begin(), node.end(), [&](int a, int b){ return order[a] < order[b]; });
        node.erase(unique(node.begin(), node.end()), node.end());

        for (int j = 1; j < m; j++){
            int u = lca(node[j], node[j - 1]), v = node[j];
            add[u]--;
            add[v]++;
        }
    }

    vector<int> res;
    auto get = [&](int u, int pre, auto&& get) -> void{
        for (int v : edg[u]){
            if (v == pre)
                continue;
            get(v, u, get);
            add[u] += add[v];
        }
        if (add[u] >= k && pre != -1)
            res.push_back(mp[{u, pre}]);
    };
    get(0, -1, get);
    cout << res.size() << endl;
    for (int i = 0; i < res.size(); i++)
        cout << res[i] << ' ';
}

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (ifstream("input.txt").good()){
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout); 
    }

    int t = 1;
    while (t--){
        solve();
        cout << "\n";
    }
}

Compilation message (stderr)

railway.cpp:112:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  112 | main(){
      | ^~~~
railway.cpp: In function 'int main()':
railway.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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