Submission #393887

#	Time	Username	Problem	Language	Result	Execution time	Memory
393887		JerryLiu06	Railway (BOI17_railway)	C++11	100 / 100	102 ms	23320 KiB

railway

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

int N, M, K, timer = 1; vector<int> adj[100010];

int in[100010], out[100010], lift[100010][20];

int pref[100010], U[100010], V[100010];

void DFS(int X, int P) {
    in[X] = timer++; lift[X][0] = P;

    for (int NXT : adj[X]) if (NXT != P) { DFS(NXT, X); } out[X] = timer - 1;
}
bool isAnc(int A, int B) { return in[A] <= in[B] && out[A] >= out[B]; }

int getLCA(int A, int B) {
    if (isAnc(A, B)) return A; if (isAnc(B, A)) return B;

    for (int i = 19; i >= 0; i--) {
        if (lift[A][i] && !isAnc(lift[A][i], B)) A = lift[A][i];
    }
    return lift[A][0];
}

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

    cin >> N >> M >> K;

    for (int i = 1; i < N; i++) { cin >> U[i] >> V[i]; adj[U[i]].pb(V[i]), adj[V[i]].pb(U[i]); }
    
    DFS(1, 0); for (int j = 1; j < 20; j++) for (int i = 1; i <= N; i++) lift[i][j] = lift[lift[i][j - 1]][j - 1];

    for (int i = 0; i < M; i++) {
        int S; cin >> S; int A[S]; for (int i = 0; i < S; i++) cin >> A[i];

        sort(A, A + S, [](int A, int B) { return in[A] < in[B]; });

        for (int i = 0; i < S; i++) {
            int X = A[i]; int Y = A[(i + 1) % S]; if (in[X] > in[Y]) swap(X, Y);
            
            if (isAnc(X, Y)) { pref[in[X]]--, pref[in[Y]]++; continue; }

            int LCA = getLCA(X, Y); pref[in[X]]++; pref[in[Y]]++; pref[in[LCA]] -= 2;
        }
    }
    for (int i = 1; i < timer; i++) pref[i] += pref[i - 1];

    vector<int> ans; for (int i = 1; i < N; i++) {
        int LOW = (isAnc(U[i], V[i])) ? V[i] : U[i];

        if (pref[out[LOW]] - pref[in[LOW] - 1] >= 2 * K) ans.pb(i);
    }
    cout << ans.size() << "\n"; for (int i : ans) cout << i << " ";
}

Compilation message (stderr)

railway.cpp: In function 'void DFS(int, int)':
railway.cpp:16:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   16 |     for (int NXT : adj[X]) if (NXT != P) { DFS(NXT, X); } out[X] = timer - 1;
      |     ^~~
railway.cpp:16:59: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   16 |     for (int NXT : adj[X]) if (NXT != P) { DFS(NXT, X); } out[X] = timer - 1;
      |                                                           ^~~
railway.cpp: In function 'int getLCA(int, int)':
railway.cpp:21:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   21 |     if (isAnc(A, B)) return A; if (isAnc(B, A)) return B;
      |     ^~
railway.cpp:21:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   21 |     if (isAnc(A, B)) return A; if (isAnc(B, A)) return B;
      |                                ^~

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