Submission #357765

#	Time	Username	Problem	Language	Result	Execution time	Memory
357765		parsabahrami	Railway (BOI17_railway)	C++17	100 / 100	166 ms	28012 KiB

railway

// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 1e5 + 10;
int tim, n, m, k, St[N], Ft[N], P[19][N], H[N], from[N], to[N], ps[N]; vector<int> adj[N], R;

void preDFS(int v, int p = -1) {
    if (!~p) P[0][v] = v;
    St[v] = tim++;
    for (int i = 1; i < 19; i++) P[i][v] = P[i - 1][P[i - 1][v]];
    for (int id : adj[v]) {
        int u = from[id] ^ to[id] ^ v;
        if (u != p) {
            H[u] = H[v] + 1;
            P[0][u] = v; 
            preDFS(u, v);
        }
    }
    Ft[v] = tim;
}

int getpar(int v, int h) {
    for (int i = h; i; i -= i & -i) v = P[__builtin_ctz(i)][v];
    return v;
}

int LCA(int u, int v) {
    if (H[u] < H[v]) swap(u, v);
    u = getpar(u, H[u] - H[v]);
    if (u == v) return v;
    for (int i = 18; ~i; i--) if (P[i][u] != P[i][v]) v = P[i][v], u = P[i][u];
    return P[0][v];
}

void DFS(int v, int p = -1) {
    for (int id : adj[v]) {
        int u = from[id] ^ to[id] ^ v;
        if (u != p) {
            DFS(u, v);
            ps[v] += ps[u];
            if (ps[u] >= k) R.push_back(id);
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &from[i], &to[i]);
        adj[to[i]].push_back(i);
        adj[from[i]].push_back(i);
    }
    preDFS(1);
    for (int _ = 1, l; _ <= m; _++) {
        vector<int> vec; 
        for (scanf("%d", &l); l; l--) {
            int v; scanf("%d", &v); vec.push_back(v);
        }
        int sz = SZ(vec);
        sort(vec.begin(), vec.end(), [&] (int u, int v) { return St[u] < St[v]; });
        for (int i = 0; i < sz; i++) {
            int u = vec[(i + 1) % sz], v = vec[i];
            int p = LCA(u, v);
            vec.push_back(p);
        }
        sort(vec.begin(), vec.end(), [&] (int u, int v) { return St[u] < St[v]; });
        vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
        stack<int> st;
        st.push(vec[0]);
        for (int i = 1; i < SZ(vec); i++) {
            int v = vec[i];
            while (!(St[st.top()] <= St[v] && Ft[v] <= Ft[st.top()])) st.pop();
            ps[v]++, ps[st.top()]--;
            st.push(v);
        }
    }
    DFS(1);
    sort(R.begin(), R.end());
    printf("%d\n", SZ(R));
    for (int &i : R) printf("%d ", i);
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |     scanf("%d%d%d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |         scanf("%d%d", &from[i], &to[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:65:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |         for (scanf("%d", &l); l; l--) {
      |              ~~~~~^~~~~~~~~~
railway.cpp:66:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |             int v; scanf("%d", &v); vec.push_back(v);
      |                    ~~~~~^~~~~~~~~~

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