Submission #1096139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096139		Kubogi	Railway (BOI17_railway)	C++17	100 / 100	55 ms	25476 KiB

railway

#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)

const int maxn = 1e5+3, lg = 16;
int n, m, k, f[maxn], tin[maxn], tout[maxn], P[maxn][lg+1], dep[maxn];
vector<int> adj[maxn];
pair<int, int> E[maxn];

int t = 0;
void dfs0(int u = 1, int p = 0) {
    dep[u] = dep[p]+1;
    tin[u] = ++t;
    P[u][0] = p;
    for (int i = 1; i <= lg; i++) {
        P[u][i] = P[P[u][i-1]][i-1];
    }
    for (int v: adj[u]) {
        if (v != p) {
            dfs0(v, u);
        }
    }
}

int lca(int x, int y) {
    if (dep[x] > dep[y]) swap(x, y);
    for (int i = lg; i >= 0; i--) {
        if (dep[y] - (1<<i) >= dep[x]) {
            y = P[y][i];
        }
    }
    if (x == y) return x;

    for (int i = lg; i >= 0; i--) {
        if (P[x][i] != P[y][i]) {
            x = P[x][i];
            y = P[y][i];
        }
    }
    return P[x][0];
}

void dfs(int u = 1, int p = -1) {
    for (int v: adj[u]) {
        if (v != p) {
            dfs(v, u);
            f[u] += f[v];
        }
    }
}

bool cmp(const int &x, const int &y) {
    return tin[x] < tin[y];
}

int32_t main (){
    ios_base::sync_with_stdio (false);
    cin.tie (nullptr);
    fileio("");

    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        int x, y; cin >> x >> y;
        E[i] = {x, y};
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    dfs0();
    while (m--) {
        int s; cin >> s;
        vector<int> V(s);
        for (int i = 0; i < s; i++) {
            cin >> V[i];
        }
        sort(V.begin(), V.end(), cmp);

        for (int i = 0; i < s; i++) {
            f[V[i]]++; f[V[(i+1)%s]]++;
            f[lca(V[i], V[(i+1)%s])] -= 2;
        }
    }

    dfs();

    vector<int> ans;
    for (int i = 1; i < n; i++) {
        int x = E[i].first, y = E[i].second;
        if (y == P[x][0]) swap(x, y);
        if (f[y]/2 >= k) {
            ans.push_back(i);
        }
    }

    cout << ans.size() << "\n";
    for (int i: ans) {
        cout << i << " ";
    }

    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int32_t main()':
railway.cpp:5:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:61:5: note: in expansion of macro 'fileio'
   61 |     fileio("");
      |     ^~~~~~
railway.cpp:5:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define fileio(name) if (fopen(name".inp", "r")) freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout)
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:61:5: note: in expansion of macro 'fileio'
   61 |     fileio("");
      |     ^~~~~~

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